A Nullspace Property for Subspace-Preserving Recovery

Mustafa D Kaba, Chong You, Daniel P Robinson, Enrique Mallada, Rene Vidal
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5180-5188, 2021.

Abstract

Much of the theory for classical sparse recovery is based on conditions on the dictionary that are both necessary and sufficient (e.g., nullspace property) or only sufficient (e.g., incoherence and restricted isometry). In contrast, much of the theory for subspace-preserving recovery, the theoretical underpinnings for sparse subspace classification and clustering methods, is based on conditions on the subspaces and the data that are only sufficient (e.g., subspace incoherence and data inner-radius). This paper derives a necessary and sufficient condition for subspace-preserving recovery that is inspired by the classical nullspace property.Based on this novel condition, called here the subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation that relates data distribution and subspace separation to the recovery success, or can be verified using a finite set of extreme points of a properly defined set. We further exploit these characterizations to derive new sufficient conditions, based on inner-radius and outer-radius measures and dual bounds, that generalize existing conditions and preserve the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-kaba21a, title = {A Nullspace Property for Subspace-Preserving Recovery}, author = {Kaba, Mustafa D and You, Chong and Robinson, Daniel P and Mallada, Enrique and Vidal, Rene}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5180--5188}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/kaba21a/kaba21a.pdf}, url = {https://proceedings.mlr.press/v139/kaba21a.html}, abstract = {Much of the theory for classical sparse recovery is based on conditions on the dictionary that are both necessary and sufficient (e.g., nullspace property) or only sufficient (e.g., incoherence and restricted isometry). In contrast, much of the theory for subspace-preserving recovery, the theoretical underpinnings for sparse subspace classification and clustering methods, is based on conditions on the subspaces and the data that are only sufficient (e.g., subspace incoherence and data inner-radius). This paper derives a necessary and sufficient condition for subspace-preserving recovery that is inspired by the classical nullspace property.Based on this novel condition, called here the subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation that relates data distribution and subspace separation to the recovery success, or can be verified using a finite set of extreme points of a properly defined set. We further exploit these characterizations to derive new sufficient conditions, based on inner-radius and outer-radius measures and dual bounds, that generalize existing conditions and preserve the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature.} }
Endnote
%0 Conference Paper %T A Nullspace Property for Subspace-Preserving Recovery %A Mustafa D Kaba %A Chong You %A Daniel P Robinson %A Enrique Mallada %A Rene Vidal %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-kaba21a %I PMLR %P 5180--5188 %U https://proceedings.mlr.press/v139/kaba21a.html %V 139 %X Much of the theory for classical sparse recovery is based on conditions on the dictionary that are both necessary and sufficient (e.g., nullspace property) or only sufficient (e.g., incoherence and restricted isometry). In contrast, much of the theory for subspace-preserving recovery, the theoretical underpinnings for sparse subspace classification and clustering methods, is based on conditions on the subspaces and the data that are only sufficient (e.g., subspace incoherence and data inner-radius). This paper derives a necessary and sufficient condition for subspace-preserving recovery that is inspired by the classical nullspace property.Based on this novel condition, called here the subspace nullspace property, we derive equivalent characterizations that either admit a clear geometric interpretation that relates data distribution and subspace separation to the recovery success, or can be verified using a finite set of extreme points of a properly defined set. We further exploit these characterizations to derive new sufficient conditions, based on inner-radius and outer-radius measures and dual bounds, that generalize existing conditions and preserve the geometric interpretations. These results fill an important gap in the subspace-preserving recovery literature.
APA
Kaba, M.D., You, C., Robinson, D.P., Mallada, E. & Vidal, R.. (2021). A Nullspace Property for Subspace-Preserving Recovery. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5180-5188 Available from https://proceedings.mlr.press/v139/kaba21a.html.

Related Material