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.

Whether you’re looking for clothes, electronics, or anything in between, Gulf News Discounts has you covered. We make it easy to find the best deals on the products you want, so you can spend less time searching and more time shopping. Check us out today and start saving!

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.

Ledva, G. S., L. Balzano, and J. L. Mathieu. 2018. “Real-Time Energy Disaggregation of a Distribution Feeder’s Demand Using Online Learning.” IEEE Transactions on Power Systems, 1–1. https://doi.org/10.1109/TPWRS.2018.2800535.
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.
Eftekhari, Armin, Gregory Ongie, Laura Balzano, and Michael B. Wakin. 2019. “Streaming Principal Component Analysis From Incomplete Data.” Journal of Machine Learning Research 20 (86): 1–62. http://jmlr.org/papers/v20/16-627.html. 1
Eftekhari, A., L. Balzano, and M. B. Wakin. 2017. “What to Expect When You Are Expecting on the Grassmannian.” IEEE Signal Processing Letters 24 (6): 872–76. https://doi.org/10.1109/LSP.2017.2684784.
Pimentel-Alarcón, Daniel, Laura Balzano, and Robert Nowak. 2016. “Necessary and Sufficient Conditions for Sketched Subspace Clustering.” In Allerton Conference on Communication, Control, and Computing. https://danielpimentel.github.io/pdfs/sketchedSC.pdf.
Hong, David, Kyle Gilman, Laura Balzano, and Jeffrey A. Fessler. 2021. “HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise.” ArXiv:2101.03468 [Eess, Math, Stat], January. http://arxiv.org/abs/2101.03468. 2
Pimentel-Alarcón, D., L. Balzano, R. Marcia, R. Nowak, and R. Willett. 2016. “Group-Sparse Subspace Clustering with Missing Data.” In 2016 IEEE Statistical Signal Processing Workshop (SSP), 1–5. https://doi.org/10.1109/SSP.2016.7551734.
Zhang, Dejiao, Yifan Sun, Brian Eriksson, and Laura Balzano. 2017. “Deep Unsupervised Clustering Using Mixture of Autoencoders.” ArXiv:1712.07788 [Cs, Stat], December. http://arxiv.org/abs/1712.07788.
Ledva, Gregory, Laura Balzano, and Johanna Mathieu. 2015. “Inferring the Behavior of Distributed Energy Resources with Online Learning.” In Proceedings of the Allerton Conference on Communication, Control, and Computing.
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–75. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6247848.
Li, Yuchen, Laura Balzano, Deanna Needell, and Hanbaek Lyu. 2024. “Convergence and Complexity Guarantee for Inexact First-Order Riemannian Optimization Algorithms.” In . https://openreview.net/forum?id=7KtFQnF368.
Yaras, Can, Peng Wang, Laura Balzano, and Qing Qu. 2024. “Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation.” In . https://openreview.net/forum?id=uDkXoZMzBv.
Liu, Huikang, Peng Wang, Longxiu Huang, Qing Qu, and Laura Balzano. 2024. “Symmetric Matrix Completion with ReLU Sampling.” In . https://openreview.net/forum?id=VxI0gInNlh.
Zhang, Dejiao, Tianchen Zhao, and Laura Balzano. 2018. “INFORMATION MAXIMIZATION AUTO-ENCODING,” September. https://openreview.net/forum?id=SyVpB2RqFX.
Wang, Peng, Xiao Li, Can Yaras, Zhihui Zhu, Laura Balzano, Wei Hu, and Qing Qu. 2024. “Understanding Deep Representation Learning via Layerwise Feature Compression and Discrimination.” arXiv. https://doi.org/10.48550/arXiv.2311.02960. 3
Ongie, Greg, Rebecca Willett, Robert D. Nowak, and Laura Balzano. 2017. “Algebraic Variety Models for High-Rank Matrix Completion.” In Proceedings of the 34th International Conference on Machine Learning, 2691–2700. PMLR. https://proceedings.mlr.press/v70/ongie17a.html.
Lipor, John, and Laura Balzano. 2017. “Leveraging Union of Subspace Structure to Improve Constrained Clustering.” In Proceedings of the 34th International Conference on Machine Learning, 2130–39. PMLR. https://proceedings.mlr.press/v70/lipor17a.html.
Kwon, Soo Min, Zekai Zhang, Dogyoon Song, Laura Balzano, and Qing Qu. 2024. “Efficient Low-Dimensional Compression of Overparameterized Models.” In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, 1009–17. PMLR. https://proceedings.mlr.press/v238/min-kwon24a.html.
Tarzanagh, Davoud Ataee, Parvin Nazari, Bojian Hou, Li Shen, and Laura Balzano. 2024. “Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods.” In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, 2854–62. PMLR. https://proceedings.mlr.press/v238/ataee-tarzanagh24a.html.
Newton, Rachel, Zhe Du, Peter Seiler, and Laura Balzano. 2024. “Optimality of POD for Data-Driven LQR With Low-Rank Structures.” IEEE Control Systems Letters 8:85–90. https://doi.org/10.1109/LCSYS.2023.3344147.
Geelen, Rudy, Laura Balzano, and Karen Willcox. 2023. “Learning Latent Representations in High-Dimensional State Spaces Using Polynomial Manifold Constructions.” In 2023 62nd IEEE Conference on Decision and Control (CDC), 4960–65. https://doi.org/10.1109/CDC49753.2023.10384209.
Wang, Peng, Xiao Li, Can Yaras, Zhihui Zhu, Laura Balzano, Wei Hu, and Qing Qu. 2024. “Understanding Hierarchical Representations in Deep Networks via Feature Compression and Discrimination.” In . https://openreview.net/forum?id=Ovuu8LpGZu.
Kwon, Soo Min, Zekai Zhang, Dogyoon Song, Laura Balzano, and Qing Qu. 2024. “Efficient Low-Dimensional Compression of Overparameterized Networks.” In . https://openreview.net/forum?id=1AVb9oEdK7.
Yaras, Can, Peng Wang, Wei Hu, Zhihui Zhu, Laura Balzano, and Qing Qu. 2024. “Invariant Low-Dimensional Subspaces in Gradient Descent for Learning Deep Linear Networks.” In . https://openreview.net/forum?id=oSzCKf1I5N.
Geelen, Rudy, Laura Balzano, Stephen Wright, and Karen Willcox. 2024. “Learning Physics-Based Reduced-Order Models from Data Using Nonlinear Manifolds.” Chaos: An Interdisciplinary Journal of Nonlinear Science 34 (3): 033122. https://doi.org/10.1063/5.0170105.
Hong, David, Fan Yang, Jeffrey A. Fessler, and Laura Balzano. 2023. “Optimally Weighted PCA for High-Dimensional Heteroscedastic Data.” SIAM Journal on Mathematics of Data Science 5 (1): 222–50. https://doi.org/10.1137/22M1470244.
Kwon, Soo Min, Zekai Zhang, Dogyoon Song, Laura Balzano, and Qing Qu. 2023. “Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamics.” arXiv. https://doi.org/10.48550/arXiv.2311.05061.
Gilman, Kyle, Sam Burer, and Laura Balzano. 2023. “A Semidefinite Relaxation for Sums of Heterogeneous Quadratic Forms on the Stiefel Manifold.” arXiv. https://doi.org/10.48550/arXiv.2205.13653.
Yaras, Can, Peng Wang, Wei Hu, Zhihui Zhu, Laura Balzano, and Qing Qu. 2023. “Invariant Low-Dimensional Subspaces in Gradient Descent for Learning Deep Matrix Factorizations.” In . https://openreview.net/forum?id=4pPnQqUMLS.
Newton, Rachel, Zhe Du, Laura Balzano, and Peter Seiler. 2023. “Manifold Optimization for Data Driven Reduced-Order Modeling*.” In 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 1–6. https://doi.org/10.1109/Allerton58177.2023.10313500.
Cavazos, Javier Salazar, Jeffrey A. Fessler, and Laura Balzano. 2023. “ALPCAH: Sample-Wise Heteroscedastic PCA with Tail Singular Value Regularization.” In 2023 International Conference on Sampling Theory and Applications (SampTA), 1–6. https://doi.org/10.1109/SampTA59647.2023.10301206.
Soleymani, Mahdi, Qiang Liu, Hessam Mahdavifar, and Laura Balzano. 2023. “Matrix Completion over Finite Fields: Bounds and Belief Propagation Algorithms.” In 2023 IEEE International Symposium on Information Theory (ISIT), 1166–71. https://doi.org/10.1109/ISIT54713.2023.10206551.
Cavazos, Javier Salazar, Jeffrey A. Fessler, and Laura Balzano. 2023. “ALPCAH: Sample-Wise Heteroscedastic PCA with Tail Singular Value Regularization.” arXiv. https://doi.org/10.48550/arXiv.2307.02745. 4
Geelen, Rudy, Laura Balzano, Stephen Wright, and Karen Willcox. 2023. “Learning Physics-Based Reduced-Order Models from Data Using Nonlinear Manifolds.” arXiv. https://doi.org/10.48550/arXiv.2308.02802.
Wang, Peng, Rujun Jiang, Qingyuan Kong, and Laura Balzano. 2023. “Proximal DC Algorithm for Sample Average Approximation of Chance Constrained Programming: Convergence and Numerical Results.” arXiv. https://doi.org/10.48550/arXiv.2301.00423. 5
Yaras, Can, Peng Wang, Wei Hu, Zhihui Zhu, Laura Balzano, and Qing Qu. 2023. “The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks.” arXiv. https://doi.org/10.48550/arXiv.2306.01154. 6
Xu, Alec S., Laura Balzano, and Jeffrey A. Fessler. 2023. “HeMPPCAT: Mixtures of Probabilistic Principal Component Analysers for Data with Heteroscedastic Noise.” In ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1–5. https://doi.org/10.1109/ICASSP49357.2023.10094719.
Blocker, Cameron J., Haroon Raja, Jeffrey A. Fessler, and Laura Balzano. 2023. “Dynamic Subspace Estimation with Grassmannian Geodesics.” arXiv. https://doi.org/10.48550/arXiv.2303.14851.
Naik, Rishhabh, Nisarg Trivedi, Davoud Ataee Tarzanagh, and Laura Balzano. 2022. “Truncated Matrix Completion - An Empirical Study.” In 2022 30th European Signal Processing Conference (EUSIPCO), 847–51. https://doi.org/10.23919/EUSIPCO55093.2022.9909952.
Xu, Alec S., Laura Balzano, and Jeffrey A. Fessler. 2023. “HeMPPCAT: Mixtures of Probabilistic Principal Component Analysers for Data with Heteroscedastic Noise.” arXiv. https://doi.org/10.48550/arXiv.2301.08852.
Wang, Peng, Huikang Liu, Can Yaras, Laura Balzano, and Qing Qu. 2022. “Linear Convergence Analysis of Neural Collapse with Unconstrained Features.” In . https://openreview.net/forum?id=WC9im-M_y5.
Yaras, Can, Peng Wang, Zhihui Zhu, Laura Balzano, and Qing Qu. 2022. “Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold.” In . https://openreview.net/forum?id=Zvh6lF5b26N.
Du, Zhe, Laura Balzano, and Necmiye Ozay. 2022. “Mode Reduction for Markov Jump Systems.” IEEE Open Journal of Control Systems, 1–19. https://doi.org/10.1109/OJCSYS.2022.3212613.
Tarzanagh, Davoud Ataee, Laura Balzano, and Alfred O. Hero. 2021. “Fair Structure Learning in Heterogeneous Graphical Models.” arXiv. https://doi.org/10.48550/arXiv.2112.05128.
Hong, David, Fan Yang, Jeffrey A. Fessler, and Laura Balzano. 2022. “Optimally Weighted PCA for High-Dimensional Heteroscedastic Data.” arXiv. https://doi.org/10.48550/arXiv.1810.12862. 7
Ritchie, Alexander, Laura Balzano, Daniel Kessler, Chandra S. Sripada, and Clayton Scott. 2022. “Supervised PCA: A Multiobjective Approach.” arXiv. https://doi.org/10.48550/arXiv.2011.05309.
Balzano, Laura. 2022. “On the Equivalence of Oja’s Algorithm and GROUSE.” In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 7014–30. PMLR. https://proceedings.mlr.press/v151/balzano22a.html.
Du, Zhe, Yahya Sattar, Davoud Ataee Tarzanagh, Laura Balzano, Necmiye Ozay, and Samet Oymak. 2022. “Data-Driven Control of Markov Jump Systems: Sample Complexity and Regret Bounds.” In 2022 American Control Conference (ACC), 4901–8. https://doi.org/10.23919/ACC53348.2022.9867863.
Sattar, Yahya, Zhe Du, Davoud Ataee Tarzanagh, Samet Oymak, Laura Balzano, and Necmiye Ozay. 2022. “Certainty Equivalent Quadratic Control for Markov Jump Systems.” In 2022 American Control Conference (ACC), 2871–78. https://doi.org/10.23919/ACC53348.2022.9867208.
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-24.