Online identification and tracking of subspaces from highly incomplete information

By Laura Balzano, Robert D. Nowak, B. Recht. Allerton Conference on Communication, Control, and Computing, 2010

446 citations recorded by the source corpus.

This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of the subspace. The algorithm is derived by analyzing incremental gradient descent on the Grassmannian manifold of subspaces. With a slight modification, GROUSE can also be used as an online incremental algorithm for the matrix completion problem of imputing missing entries of a low-rank matrix. GROUSE performs exceptionally well in practice both in tracking subspaces and as an online algorithm for matrix completion.

Subfields: Artificial Intelligence, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/f97e98caf94f2c4ebf70d6800cfddc2091a910f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Parallel stochastic gradient algorithms for large-scale matrix completion (2013, background): “Such an adaptation could be useful in recommender systems where users are constantly updating their preferences and could also be extended to finding anomalies in network traffic behavior [3].”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “Deﬁne w n := arg min w (cid:107)P Ω n ( U n − 1 w − x n ) 22 ; 6: Compute the SVD of the update matrix: where for PIMC.”
Projection-based model reduction: Formulations for physics-based machine learning (2019, background): “Another line of work seeks to recover [46, 47] or to update [48, 49, 50] reduced models from sparse data.”
Low-Rank Matrix Completion by Riemannian Optimization (2012, methodology): “Other approaches include optimization on the Grassmann manifold [5, 18, 27]; atomic decompositions [33]; and nonlinear SOR [53].”
Dual Principal Component Pursuit (2015, methodology): “For methods from robust statistics see Huber (1981); Jolliffe (2002), for online subspace learning methods see Balzano et al. (2010); Feng et al. (2013), for regression-type methods see Wang et al. (2015), while for fast and other methods the reader is referred to the excellent literature review of…”
Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery (2017, methodology): “In its subspace update step, the SVD or projected-SVD used in different variants of ReProCS [18], [12], [27] are replaced by a faster but approximate subspace tracking algorithm called GROUSE [40]. pROST [51] and ROSETA.”
Incremental gradient on the Grassmannian for online foreground and background separation in subsampled video (2012, methodology): “GROUSE [2] uses the Euclidean distance, the l(2)-norm, to measure the subspace error from the subspace spanned by the columns of Ut to the observed vector vΩt : Fgrouse(S; t) = min w ‖UΩtw − vΩt‖(2)2 .”
Manopt, a matlab toolbox for optimization on manifolds (2013, background): “…the Grassmann manifold proves useful in low-rank matrix completion, where it is observed that if one knows the column space spanned by the sought matrix, then completing the matrix according to a least squares criterion is easy (Keshavan et al. , 2010; Boumal & Absil, 2011; Balzano et al. , 2010).”
Scaled Gradients on Grassmann Manifolds for Matrix Completion (2012, methodology): “Now, we compare the relaxed version of the scaled conjugate gr dient which uses (5) to computeSi (ScGrass-CG) to LMaFit [23], Riemann-CG [22], RTRMC2 [6] (trust region method with second order information), SVP [12] and GROUSE [5] (Figure 2).”
Memory Limited, Streaming PCA (2013, methodology): “In the setting of the so-called spiked covariance model (and natural generalizations) we show that a simple algorithm requiring O(kp) storage – the best possible – performs as well as batch algorithms (namely, SVD on the empirical covariance matrix), with sample complexity O(p log p).”