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.

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.
Gilman, Kyle, and Laura Balzano. 2020. “Online Tensor Completion and Free Submodule Tracking With The T-SVD.” In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 3282–86. https://doi.org/10.1109/ICASSP40776.2020.9053199.
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.
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.
Pimentel-Alarcón, D., G. Ongie, L. Balzano, R. Willett, and R. Nowak. 2017. “Low Algebraic Dimension Matrix Completion.” In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 790–97. https://doi.org/10.1109/ALLERTON.2017.8262820.
Ongie, Greg, Rebecca Willett, Robert D. Nowak, and Laura Balzano. 2017. “Algebraic Variety Models for High-Rank Matrix Completion.” In PMLR, 2691–2700. http://proceedings.mlr.press/v70/ongie17a.html.
Zhang, D., and L. Balzano. 2017. “Matched Subspace Detection Using Compressively Sampled Data.” In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 4601–5. https://doi.org/10.1109/ICASSP.2017.7953028.
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.
Ganti, Ravi Sastry, Laura Balzano, and Rebecca Willett. 2015. “Matrix Completion Under Monotonic Single Index Models.” In Proceedings of the Conference for Advances in Neural Information Processing Systems, 1864–72. http://papers.nips.cc/paper/5916-matrix-completion-under-monotonic-single-index-models.
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.
Balzano, Laura, and Stephen J. Wright. 2014. “Local Convergence of an Algorithm for Subspace Identification from Partial Data.” Foundations of Computational Mathematics, October, 1–36. http://link.springer.com/article/10.1007/s10208-014-9227-7.
Pimentel, D., R. Nowak, and L. Balzano. 2014. “On the Sample Complexity of Subspace Clustering with Missing Data.” In 2014 IEEE Workshop on Statistical Signal Processing (SSP), 280–83. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6884630.
Kennedy, R., L. Balzano, S.J. Wright, and C.J. Taylor. 2014. “Online Algorithms for Factorization-Based Structure from Motion.” In 2014 IEEE Winter Conference on Applications of Computer Vision (WACV), 37–44. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6836120.
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.
Tan, Vincent YF, Laura Balzano, and Stark C. Draper. 2012. “Rank Minimization over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations.” Information Theory, IEEE Transactions On 58 (4): 2018–2039. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6094216.
Eriksson, Brian, Laura Balzano, and Robert Nowak. 2012. “High Rank Matrix Completion.” In Proc. of Intl. Conf. on Artificial Intell. and Stat. http://jmlr.csail.mit.edu/proceedings/papers/v22/eriksson12/eriksson12.pdf. 1
Balzano, Laura, Arthur Szlam, Benjamin Recht, and Robert Nowak. 2012. “K-Subspaces with Missing Data.” In Statistical Signal Processing Workshop (SSP), 2012 IEEE, 612–615. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6319774.
Tan, Vincent YF, Laura Balzano, and Stark C. Draper. 2011. “Rank Minimization over Finite Fields.” In Information Theory Proceedings (ISIT), 2011 IEEE International Symposium On, 1195–1199. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6033722.
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.