Low-Rank Matrices on Graphs: Generalized Recovery & Applications
This work addresses the challenge of low-rank recovery for real-world datasets with unknown geometry, offering a scalable solution for applications in data analysis, though it builds incrementally on existing low-rank recovery methods.
The paper tackles the problem of recovering low-rank structures from datasets with unknown geometry, which is under-determined and often non-linear, by introducing a graph-based approach. It results in scalable algorithms with recovery guarantees, achieving approximate recovery for both linear and non-linear structures, as validated by theoretical and experimental analysis.
Many real world datasets subsume a linear or non-linear low-rank structure in a very low-dimensional space. Unfortunately, one often has very little or no information about the geometry of the space, resulting in a highly under-determined recovery problem. Under certain circumstances, state-of-the-art algorithms provide an exact recovery for linear low-rank structures but at the expense of highly inscalable algorithms which use nuclear norm. However, the case of non-linear structures remains unresolved. We revisit the problem of low-rank recovery from a totally different perspective, involving graphs which encode pairwise similarity between the data samples and features. Surprisingly, our analysis confirms that it is possible to recover many approximate linear and non-linear low-rank structures with recovery guarantees with a set of highly scalable and efficient algorithms. We call such data matrices as \textit{Low-Rank matrices on graphs} and show that many real world datasets satisfy this assumption approximately due to underlying stationarity. Our detailed theoretical and experimental analysis unveils the power of the simple, yet very novel recovery framework \textit{Fast Robust PCA on Graphs}