Abstract
High-dimensional data often lie in low-dimensional subspaces corresponding to different classes they belong to. Finding sparse representations of data points in a dictionary built using the collection of data helps to uncover low-dimensional subspaces and address problems such as clustering, classification, subset selection and more. In this paper, we address the problem of recovering sparse representations for noisy data points in a dictionary whose columns correspond to corrupted data lying close to a union of subspaces. We consider a constrained $\ell_1$-minimization and study conditions under which the solution of the proposed optimization satisfies the approximate subspace-sparse recovery condition. More specifically, we show that each noisy data point, perturbed from a subspace by a noise of the magnitude of $\varepsilon$, will be reconstructed using data points from the same subspace with a small error of the order of $O(\varepsilon)$ and that the coefficients corresponding to data points in other subspaces will be sufficiently small, i.e., of the order of $O(\varepsilon)$. We do not impose any randomness assumption on the arrangement of subspaces or distribution of data points in each subspace. Our framework is based on a novel generalization of the null-space property to the setting where data lie in multiple subspaces, the number of data points in each subspace exceeds the dimension of the subspace, and all data points are corrupted by noise. Moreover, assuming a random distribution for data points, we further show that coefficients from the desired support not only reconstruct a given point with high accuracy, but also have sufficiently large values, i.e., of the order of $O(1)$.
Introduction
In many high-dimensional data applications, such as computer vision and signal processing, data points do not fill the entire ambient space but instead cluster around a union of low-dimensional subspaces. For example, images of a face under different lighting conditions typically lie near a low-dimensional linear subspace. Identifying these subspaces is a fundamental task, often addressed through Sparse Subspace Clustering (SSC).
SSC relies on the "self-expression" property: a data point can be represented as a sparse linear combination of other points from the same subspace. While existing theory often assumes a clean dictionary, real-world data is almost always noisy. This paper provides the first rigorous theoretical guarantees for recovering sparse representations when both the query points and the dictionary are corrupted by noise.
Methodology
The authors propose using constrained $\ell_1$-minimization to recover sparse representations: $$\min \|c\|_1 \quad \text{subject to} \quad \|y - Yc\|_2 \leq \gamma\epsilon$$ where $y$ is a noisy query point, $Y$ is a dictionary of noisy data points, $\epsilon$ is the noise magnitude, and $\gamma$ is a regularization parameter.
To analyze this, they introduce a Noisy Multi-Subspace Null-Space Property. This is a novel generalization of the standard null-space property from compressed sensing, specifically designed for the "self-dictionary" setting where the number of points in a subspace often exceeds its dimension and every column in the dictionary is corrupted.
Geometric Analysis and Recovery Conditions
The success of the recovery depends on the interplay between the distribution of points within subspaces and the separation between the subspaces themselves. Two key parameters are defined:
- Subspace Inradius ($r_i$): This measures how well points $\mathcal{P}_i$ cover their respective subspace $\mathcal{S}_i$. A larger inradius indicates a more uniform distribution of points, which facilitates better representation.
- Subspace Incoherence ($\mu_i$): This quantifies the distinctness or separation between different subspaces.
The authors prove that successful recovery is guaranteed if the "gap" between subspaces is larger than the noise level plus the internal voids in the data distribution, expressed as $\mu_i + \epsilon < r_i$.
Key Results
- Approximate Recovery: The solution $c^*$ accurately reconstructs the point using only points from the correct subspace $Y_i$, with an error bounded by $\|y - Y_i c_i^*\|_2 \leq \beta\epsilon$.
- Small Leakage: Coefficients assigned to points in incorrect subspaces (leakage) are bounded by $O(\epsilon)$.
- Deterministic Guarantees: The results hold for fixed, deterministic subspace arrangements, removing the need for common randomness assumptions.
- Support Detection: Under random data distribution within subspaces, the coefficients for the correct subspace are shown to be $O(1)$, making them easily distinguishable from noise-induced coefficients.
Conclusion and Future Work
This work establishes a robust theoretical framework for sparse recovery in the presence of corrupted dictionaries. While the geometric results are general, future work could explore relaxing the Gaussian noise assumption used for probabilistic bounds and developing more efficient algorithms to scale these guarantees to massive datasets. Additionally, practical methods for tuning the error tolerance $\gamma\epsilon$ remain an important area for empirical research.
Summary updated