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.

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. 1
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. 2
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. 3
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. 4
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. 5
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. 6
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, 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.