Compressive PCA for Low-Rank Matrices on Graphs - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Signal and Information Processing over Networks Year : 2016

Compressive PCA for Low-Rank Matrices on Graphs

(1) , (1) , (2, 3) , (2, 1)
1
2
3

Abstract

We introduce a novel framework for an approximate recovery of data matrices which are low-rank on graphs, from sampled measurements. The rows and columns of such matrices belong to the span of the first few eigenvectors of the graphs constructed between their rows and columns. We leverage this property to recover the non-linear low-rank structures efficiently from sampled data measurements, with a low cost (linear in n). First, a restricted Isometry Property (RIP) condition is introduced for efficient uniform sampling of the rows and columns of such matrices based on the cumulative coherence of graph eigenvectors. Secondly, a state-of-the-art fast low-rank recovery method is suggested for the sampled data. Finally, several efficient, parallel and parameter-free decoders are presented along with their theoretical analysis for decoding the low-rank and cluster indicators for the full data matrix. Thus, we overcome the computational limitations of the standard linear low-rank recovery methods for big datasets. Our method can also be seen as a major step towards efficient recovery of non-linear low-rank structures. For a matrix of size n x p, on a single core machine, our method gains a speed up of p^2 /k over Robust Principal Component Analysis (RPCA), where k << p is the subspace dimension. Numerically, we can recover a low-rank matrix of size 10304 x 1000, 100 times faster than Robust PCA.
Fichier principal
Vignette du fichier
FINAL VERSION.pdf (1.94 Mo) Télécharger le fichier
Vignette du fichier
appendices.pdf (485.74 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)

Dates and versions

hal-01277625 , version 1 (22-02-2016)
hal-01277625 , version 2 (04-01-2017)

Identifiers

Cite

Nauman Shahid, Nathanael Perraudin, Gilles Puy, Pierre Vandergheynst. Compressive PCA for Low-Rank Matrices on Graphs. IEEE Transactions on Signal and Information Processing over Networks, 2016, pp.17. ⟨10.1109/TSIPN.2016.2631890⟩. ⟨hal-01277625v2⟩
268 View
256 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More