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.

Yaras, Can, Peng Wang, Wei Hu, Zhihui Zhu, Laura Balzano, and Qing Qu. 2023. “Invariant Low-Dimensional Subspaces in Gradient Descent for Learning Deep Linear Networks.” In . https://openreview.net/forum?id=oSzCKf1I5N.
Kwon, Soo Min, Zekai Zhang, Dogyoon Song, Laura Balzano, and Qing Qu. 2023. “Efficient Low-Dimensional Compression of Overparameterized Networks.” In . https://openreview.net/forum?id=1AVb9oEdK7.
Wang, Peng, Xiao Li, Can Yaras, Zhihui Zhu, Laura Balzano, Wei Hu, and Qing Qu. 2023. “Understanding Hierarchical Representations in Deep Networks via Feature Compression and Discrimination.” In . https://openreview.net/forum?id=Ovuu8LpGZu.
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. 1
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. 2
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. 3
Geelen, Rudy, Laura Balzano, and Karen Willcox. 2023. “Learning Latent Representations in High-Dimensional State Spaces Using Polynomial Manifold Constructions.” arXiv. https://doi.org/10.48550/arXiv.2306.13748.
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.
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.
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. 4
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.
Du, Zhe, Laura Balzano, and Necmiye Ozay. 2022. “Mode Reduction for Markov Jump Systems.” https://aps.arxiv.org/abs/2205.02697.
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.
Wang, Peng, Huikang Liu, Anthony Man-Cho So, and Laura Balzano. 2022. “Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering.” In Proceedings of the 39th International Conference on Machine Learning, 22884–918. PMLR. https://proceedings.mlr.press/v162/wang22r.html.
Tarzanagh, Davoud Ataee, and Laura Balzano. 2022. “Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods.” arXiv. https://doi.org/10.48550/arXiv.2207.02829.
Wang, Peng, Huikang Liu, Anthony Man-Cho So, and Laura Balzano. 2022. “Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering.” arXiv. https://doi.org/10.48550/arXiv.2206.05553. 5
Du, Zhe, Necmiye Ozay, and Laura Balzano. 2022. “Clustering-Based Mode Reduction for Markov Jump Systems.” In Proceedings of The 4th Annual Learning for Dynamics and Control Conference, 689–701. PMLR. https://proceedings.mlr.press/v168/du22a.html.
Sattar, Yahya, Zhe Du, Davoud Ataee Tarzanagh, Laura Balzano, Necmiye Ozay, and Samet Oymak. 2021. “Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds.” arXiv. https://doi.org/10.48550/arXiv.2111.07018.
Gilman, Kyle, Sam Burer, and Laura Balzano. 2022. “A Semidefinite Relaxation for Sums of Heterogeneous Quadratics on the Stiefel Manifold.” arXiv. https://doi.org/10.48550/arXiv.2205.13653. 6
Gilman, Kyle, Davoud Ataee Tarzanagh, and Laura Balzano. 2022. “Grassmannian Optimization for Online Tensor Completion and Tracking With the T-SVD.” IEEE Transactions on Signal Processing 70: 2152–67. https://doi.org/10.1109/TSP.2022.3164837.
Zhang, Dejiao, and Laura Balzano. 2022. “Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation From Undersampled Data.” University of Michigan Technical Report, February. https://doi.org/10.7302/4151.
Ongie, Greg, Saket Dewangan, Jeffrey A. Fessler, and Laura Balzano. 2017. “Online Dynamic MRI Reconstruction via Robust Subspace Tracking.” In 2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP), 1180–84. https://doi.org/10.1109/GlobalSIP.2017.8309147.
Ledva, Gregory S., Zhe Du, Laura Balzano, and Johanna L. Mathieu. 2018. “Disaggregating Load by Type from Distribution System Measurements in Real Time.” In Energy Markets and Responsive Grids, edited by Sean Meyn, Tariq Samad, Ian Hiskens, and Jakob Stoustrup, 162:413–37. New York, NY: Springer New York. https://doi.org/10.1007/978-1-4939-7822-9_17.
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.
Bower, Amanda, and Laura Balzano. 2020. “Preference Modeling with Context-Dependent Salient Features.” In International Conference on Machine Learning, 1067–77. PMLR. https://proceedings.mlr.press/v119/bower20a.html.
Hong, David, Kyle Gilman, Laura Balzano, and Jeffrey A. Fessler. 2021. “HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise.” IEEE Transactions on Signal Processing, 1–1. https://doi.org/10.1109/TSP.2021.3104979.
Lipor, John, David Hong, Yan Shuo Tan, and Laura Balzano. 2021. “Subspace Clustering Using Ensembles of K-Subspaces.” Information and Inference: A Journal of the IMA 10 (1): 73–107. https://doi.org/10.1093/imaiai/iaaa031.
Ongie, Greg, Daniel Pimentel-Alarcón, Laura Balzano, Rebecca Willett, and Robert D. Nowak. 2021. “Tensor Methods for Nonlinear Matrix Completion.” SIAM Journal on Mathematics of Data Science, January, 253–79. https://doi.org/10.1137/20M1323448.
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. 7
Lyu, Hanbaek, Deanna Needell, and Laura Balzano. 2020. “Online Matrix Factorization for Markovian Data and Applications to Network Dictionary Learning.” Journal of Machine Learning Research 21 (251): 1–49. http://jmlr.org/papers/v21/20-444.html.
Hong, David, Shunbo Lei, Johanna L. Mathieu, and Laura Balzano. 2019. “Exploration of Tensor Decomposition Applied to Commercial Building Baseline Estimation.” In 2019 IEEE Global Conference on Signal and Information Processing (GlobalSIP), 1–5. https://doi.org/10.1109/GlobalSIP45357.2019.8969417.
Bower, Amanda, and Laura Balzano. 2020. “Preference Modeling with Context-Dependent Salient Features.” Accepted to ICML, February. http://arxiv.org/abs/2002.09615.
Du, Zhe, Laura Balzano, and Necmiye Ozay. 2018. “A Robust Algorithm for Online Switched System Identification.” IFAC-PapersOnLine, 18th IFAC Symposium on System Identification SYSID 2018, 51 (15): 293–98. https://doi.org/10.1016/j.ifacol.2018.09.150.
Ongie, Greg, David Hong, Dejiao Zhang, and Laura Balzano. 2018. “Online Estimation of Coherent Subspaces with Adaptive Sampling.” In 2018 IEEE Statistical Signal Processing Workshop (SSP), 841–45. https://doi.org/10.1109/SSP.2018.8450830.
Zhang, Dejiao, Julian Katz-Samuels, Mário A.T. Figueiredo, and Laura Balzano. 2018. “Simultaneous Sparsity and Parameter Tying for Deep Learning Using Ordered Weighted ℓ1 Regularization.” In 2018 IEEE Statistical Signal Processing Workshop (SSP), 65–69. https://doi.org/10.1109/SSP.2018.8450819.