Learning Mixtures of Low-Rank Models

Yanxi Chen, Cong Ma, H. Vincent Poor, Yuxin Chen

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.

Parameter settings for the three-stage meta-algorithm.

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

Abstract

We study the problem of learning mixtures of low-rank models, i.e. reconstructing multiple low-rank matrices from unlabelled linear measurements of each. This problem enriches two widely studied settings - low-rank matrix sensing and mixed linear regression - by bringing latent variables (i.e. unknown labels) and structural priors (i.e. low-rank structures) into consideration. To cope with the non-convexity issues arising from unlabelled heterogeneous data and low-complexity structure, we develop a three-stage meta-algorithm that is guaranteed to recover the unknown matrices with near-optimal sample and computational complexities under Gaussian designs. In addition, the proposed algorithm is provably stable against random noise. We complement the theoretical studies with empirical evidence that confirms the efficacy of our algorithm.
BibTeX
@article{chen2021learning,
  author = {Yanxi Chen and Cong Ma and H. Vincent Poor and Yuxin Chen},
  title = {{Learning Mixtures of Low-Rank Models}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  doi = {10.1109/tit.2021.3065700},
}
Figure