Rank/Norm Regularization with Closed-Form Solutions: Application to Subspace Clustering

Yao-Liang Yu, Dale Schuurmans
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:856-866, 2011.

Abstract

When data is sampled from an unknown subspace, principal component analysis (PCA) provides an effective way to estimate the subspace and hence reduce the dimension of the data. At the heart of PCA is the Eckart-Young-Mirsky theorem, which characterizes the best rank k approximation of a matrix. In this paper, we prove a generalization of the Eckart-Young-Mirsky theorem under all unitarily invariant norms. Using this result, we obtain closed-form solutions for a set of rank/norm regularized problems, and derive closed-form solutions for a general class of subspace clustering problems (where data is modelled by unions of unknown subspaces). From these results we obtain new theoretical insights and promising experimental results.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-yu11a, title = {Rank/Norm Regularization with Closed-Form Solutions: Application to Subspace Clustering}, author = {Yu, Yao-Liang and Schuurmans, Dale}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {856--866}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/yu11a/yu11a.pdf}, url = {https://proceedings.mlr.press/r9/yu11a.html}, abstract = {When data is sampled from an unknown subspace, principal component analysis (PCA) provides an effective way to estimate the subspace and hence reduce the dimension of the data. At the heart of PCA is the Eckart-Young-Mirsky theorem, which characterizes the best rank k approximation of a matrix. In this paper, we prove a generalization of the Eckart-Young-Mirsky theorem under all unitarily invariant norms. Using this result, we obtain closed-form solutions for a set of rank/norm regularized problems, and derive closed-form solutions for a general class of subspace clustering problems (where data is modelled by unions of unknown subspaces). From these results we obtain new theoretical insights and promising experimental results.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Rank/Norm Regularization with Closed-Form Solutions: Application to Subspace Clustering %A Yao-Liang Yu %A Dale Schuurmans %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-yu11a %I PMLR %P 856--866 %U https://proceedings.mlr.press/r9/yu11a.html %V R9 %X When data is sampled from an unknown subspace, principal component analysis (PCA) provides an effective way to estimate the subspace and hence reduce the dimension of the data. At the heart of PCA is the Eckart-Young-Mirsky theorem, which characterizes the best rank k approximation of a matrix. In this paper, we prove a generalization of the Eckart-Young-Mirsky theorem under all unitarily invariant norms. Using this result, we obtain closed-form solutions for a set of rank/norm regularized problems, and derive closed-form solutions for a general class of subspace clustering problems (where data is modelled by unions of unknown subspaces). From these results we obtain new theoretical insights and promising experimental results. %Z Reissued by PMLR on 04 October 2026.
APA
Yu, Y. & Schuurmans, D.. (2011). Rank/Norm Regularization with Closed-Form Solutions: Application to Subspace Clustering. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:856-866 Available from https://proceedings.mlr.press/r9/yu11a.html. Reissued by PMLR on 04 October 2026.

Related Material