Subspace Tracking

Data in the real world often have a great deal of structure. One way to capture that structure is with principal components or singular vectors. If one is interested in the best k vectors to approximate a dataset, the top k singular vectors provide exactly that. These vectors span the best-fit subspace to the data. I study the estimation of these subspaces as well as algorithms to track subspaces that change over time. I’m interested in understanding the impact of singular value gaps, noise, and corruption on subspace estimation and tracking.

For code, see posts on GROUSE, an l2 subspace tracking algorithm, GRASTA, an l1 subspace tracking algorithm, its Open CV version GRASTAcam, and TGRASTA, an algorithm that estimates a subspace under non-linear transformations.

Gilman, Kyle, and Laura Balzano. 2019. “Panoramic Video Separation with Online Grassmannian Robust Subspace Estimation.” In Proceedings of the IEEE International Conference on Computer Vision Workshops. http://openaccess.thecvf.com/content_ICCVW_2019/html/RSL-CV/Gilman_Panoramic_Video_Separation_with_Online_Grassmannian_Robust_Subspace_Estimation_ICCVW_2019_paper.html.
Balzano, L., Y. Chi, and Y. M. Lu. 2018. “Streaming PCA and Subspace Tracking: The Missing Data Case.” Proceedings of the IEEE, 1–18. https://doi.org/10.1109/JPROC.2018.2847041.
Ongie, Gregory, David Hong, Dejiao Zhang, and Laura Balzano. 2017. “Enhanced Online Subspace Estimation via Adaptive Sensing.” In Asilomar Confernce on Signals, Systems, and Computers. https://pdfs.semanticscholar.org/ba2f/61c45e92ae471552d55a8350f7211b02e6b0.pdf.
Kennedy, Ryan, Laura Balzano, Stephen J. Wright, and Camillo J. Taylor. 2016. “Online Algorithms for Factorization-Based Structure from Motion.” Computer Vision and Image Understanding 150 (September): 139–52. https://doi.org/10.1016/j.cviu.2016.04.011.
Hong, D., L. Balzano, and J. A. Fessler. 2016. “Towards a Theoretical Analysis of PCA for Heteroscedastic Data.” In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 496–503. https://doi.org/10.1109/ALLERTON.2016.7852272.
Xiao, P., and L. Balzano. 2016. “Online Sparse and Orthogonal Subspace Estimation from Partial Information.” In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 284–91. https://doi.org/10.1109/ALLERTON.2016.7852242.
Zhang, Dejiao, and Laura Balzano. 2016. “Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation.” In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 1460–68. http://jmlr.org/proceedings/papers/v51/zhang16b.html.
Kennedy, R., C.J. Taylor, and L. Balzano. 2014. “Online Completion of Ill-Conditioned Low-Rank Matrices.” In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), 507–11. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=7032169.
He, Jun, Dejiao Zhang, Laura Balzano, and Tao Tao. 2014. “Iterative Grassmannian Optimization for Robust Image Alignment.” Image and Vision Computing, Best of Automatic Face and Gesture Recognition 2013, 32 (10): 800–813. http://www.sciencedirect.com/science/article/pii/S0262885614000523.
Jun He, Laura Balzano, and Arthur Szlam. 2014. “Online Robust Background Modeling via Alternating Grassmannian Optimization.” In Background Modeling and Foreground Detection for Video Surveillance, 16-1-16–26. Chapman and Hall/CRC. http://dx.doi.org/10.1201/b17223-20.
Balzano, L., and S.J. Wright. 2013. “On GROUSE and Incremental SVD.” In 2013 IEEE 5th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 1–4. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6713992.
Balzano, Laura, and Stephen J. Wright. 2013. “Local Convergence of an Algorithm for Subspace Identification from Partial Data.” ArXiv e-print 1306.3391. http://arxiv.org/abs/1306.3391. 1
He, Jun, Laura Balzano, and Arthur Szlam. 2012. “Incremental Gradient on the Grassmannian for Online Foreground and Background Separation in Subsampled Video.” In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference On, 1568–1575. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6247848.
Balzano, Laura, Robert Nowak, and Benjamin Recht. 2010. “Online Identification and Tracking of Subspaces from Highly Incomplete Information.” In Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference On, 704–711. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5706976.
Balzano, Laura, Benjamin Recht, and Robert Nowak. 2010. “High-Dimensional Matched Subspace Detection When Data Are Missing.” In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium On, 1638–1642. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5513344.