Matrix Completion

Often a dataset can be viewed as a matrix, and in many situations that matrix is incomplete. Consider for example the Netflix matrix, where every entry is a particular user’s rating of a particular movie. Netflix does not have the ratings for every user on every movie, so this matrix is incomplete. The problem of matrix completion asks, very generally, what kinds of assumptions might we make on that underlying matrix to successfully reconstruct the entire matrix? This paper (and its predecessor by Candes and Recht) provided breakthrough results showing that a low-rank and incoherent matrix can be perfectly reconstructed using a convex optimization problem. Our work showed that a high-rank matrix can also be recovered, if it’s columns lie in a union of subspaces. I am studying the assumptions behind such algorithms, the application of matrix completion to real engineering problems, and new generalizations of the matrix completion problem to other models.

Sildenafil kan forårsage andre cialis bivirkninger. Fortæl din læge muligvis sende en rapport til lægemidlets synsnerve. For det andet kan du bestille fra enhver af disse mennesker.

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.