Abstract
Mixed matrix sensing involves the reconstruction of multiple low-rank matrices from a combined pool of unlabeled linear measurements. This paper introduces a robust three-stage framework that combines spectral subspace estimation with a specialized gradient descent variant. Our approach provides the first algorithm with near-optimal sample complexity and provable stability against noise for this non-convex problem.
Introduction
The challenge of learning mixtures of low-rank models sits at the intersection of low-rank matrix sensing and mixed linear regression. In this setting, data is received from several different sources, but the labels identifying the source of each data point are missing. Each source is characterized by a low-rank structure. The primary difficulties arise from the non-convexity of the optimization landscape and the presence of latent variables (the missing labels), which complicate the determination of optimization directions.
Methodology
The proposed "meta-algorithm" consists of three distinct stages designed to transition from a coarse global understanding to fine-grained individual matrix recovery.
Stage 1: Subspace Estimation
Using a spectral method, the algorithm estimates the joint column and row spaces shared by all $K$ unknown matrices. This stage demonstrates that labels are not strictly necessary to identify the general neighborhood of the solution.
Stage 2: Low-Dimensional Initialization
The problem is projected into the subspace identified in Stage 1, reducing the dimensionality from $n \times n$ to $R \times R$. A tensor method is then applied in this reduced space to obtain a rough initial estimate of each individual matrix.
Stage 3: Local Refinement (ScaledTGD)
The final stage utilizes Scaled Truncated Gradient Descent (ScaledTGD). The "scaled" component uses a pre-conditioner to ensure rapid convergence even for ill-conditioned matrices. The "truncated" component ignores samples with the highest loss in each step, effectively filtering out outliers—samples likely belonging to different matrices—and allowing the algorithm to focus on one matrix at a time.
The specific parameters for these stages, including rank definitions and step sizes, are detailed in the algorithmic framework above.
Key Insights
A central innovation is the use of subspace projection as a buffer, which decouples the "curse of dimensionality" from the "complexity of the mixture." Solving the mixture problem in a small $R \times R$ space is both computationally and statistically efficient. Furthermore, truncation acts as a soft clustering mechanism, allowing the algorithm to "self-label" data during gradient descent without explicit Expectation-Maximization (EM) iterations.
Results and Validation
The framework was validated using synthetic Gaussian designs, where entries of the design matrices were drawn i.i.d. from a standard Gaussian distribution. Testing on mixtures of $K=3$ matrices with dimensions $n=120$ and rank $r=2$ yielded several key findings:
- Exact Recovery: In noise-free environments, the algorithm recovers ground-truth matrices exactly (up to global permutation).
- Linear Convergence: The refinement stage converges at a geometric rate.
- Noise Robustness: Recovery error scales linearly with noise level $\sigma$, as the truncation logic prevents mislabeled samples from biasing the estimates.
- Sample Complexity: The algorithm requires a sample size of $O(n \log n)$, which is near-optimal for matrix recovery.
Conclusion
While the current framework achieves near-optimal scaling with matrix dimension, future work is needed to improve dependency on the number of components ($K$) and rank ($r$). Additionally, extending these guarantees beyond Gaussian designs to structured or sparse patterns, such as those found in mixed matrix completion, remains an important research direction.
Summary updated