Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization

Y. Shen, Z. Wen, Y. ZhangOptim. Methods Softw 2014 · DOI

TL;DR

This paper introduces a new, faster algorithm (LMaFit) for separating a low-rank matrix and a sparse matrix from their sum. Unlike previous methods that rely on computationally expensive Singular Value Decompositions (SVDs), LMaFit uses a low-rank factorization approach, leading to significant speedups and improved scalability for large-scale problems.

What Problem Does This Paper Address?

Many real-world problems involve decomposing a matrix into two components: one that is inherently low-rank (meaning it can be represented by a small number of basis vectors) and another that is sparse (meaning most of its entries are zero). Examples include separating background from foreground in videos, identifying principal components in noisy data, and recovering corrupted data. The standard approach to this "sparse matrix separation" problem involves minimizing the sum of the nuclear norm (a proxy for low-rankness) and the L1 norm (a proxy for sparsity). However, these methods require frequent SVD computations, which become prohibitively slow as matrix dimensions and ranks increase. This paper aims to overcome this computational bottleneck by proposing a new model and algorithm that avoids SVDs altogether.

Methods

The core of the paper is the introduction of a new optimization model that replaces the nuclear norm minimization with a low-rank factorization of the low-rank component. Specifically, a low-rank matrix $L$ is represented as a product of two smaller matrices, $L = UV$. This transforms the problem into a non-convex optimization problem. To solve this, the authors employ an Augmented Lagrangian Alternating Direction Method (ALADM), which they call LMaFit. This method iteratively updates the factors $U$, $V$, and the sparse matrix $Z$ by minimizing the augmented Lagrangian function with respect to each variable while keeping others fixed. Crucially, the updates for $U$ and $V$ involve solving simple least-squares problems, and the update for $Z$ uses a soft-thresholding operation, both of which are computationally efficient and avoid SVDs. The paper also discusses a rank estimation technique based on QR factorization to help determine the appropriate rank $k$ for the low-rank matrix.

Datasets

The paper evaluates its proposed method, LMaFit, on several types of synthetic and real-world datasets:

  • Fully random test problems: Generated matrices where both the low-rank and sparse components are random.
  • Semi-random problems: Where either the low-rank or the sparse matrix is deterministic (e.g., an image) and the other is random.
  • Deterministic problems: Specifically, video background extraction problems.
  • Matrix completion with corrupted data: Problems where only a subset of entries are observed, and some are corrupted by impulsive noise.

The authors do not introduce new benchmark datasets but rather use standard problem generation procedures and real-world video data.

Key Insights and Ideas

  • SVD-free approach is key to speed: The most significant insight is that by reformulating the problem to avoid explicit SVD computations, a substantial speedup can be achieved, making the method scalable to much larger problems.
  • Non-convexity doesn't always mean failure: While the low-rank factorization model is non-convex, the proposed ALADM algorithm demonstrates empirically reliable performance, often achieving comparable or better recoverability than convex methods.
  • Magnitude matters for sparse matrices: A key limitation is that the method struggles when the sparse matrix's magnitude significantly dominates that of the low-rank matrix. This suggests that the relative magnitudes of the components are crucial for the algorithm's success.
  • Rank estimation is important but flexible: While an accurate rank estimate is beneficial, the method appears to be somewhat robust to initial rank choices, especially for well-conditioned low-rank matrices.
  • Complementary to nuclear-norm methods: LMaFit extends the range of solvable problems, particularly in scenarios where incoherence assumptions (often required for theoretical guarantees in nuclear-norm methods) might not hold.

Key Results

  • Speedup: LMaFit achieves speedups of up to one to two orders of magnitude compared to state-of-the-art nuclear-norm minimization algorithms (like IALM and LRSD) on large-scale problems.
  • Recoverability: In many cases, LMaFit demonstrates comparable or superior recoverability, especially for problems with higher ranks or densities, and in situations where nuclear-norm methods struggle.
  • Robustness to noise and partial data: The method shows good performance in matrix completion problems with corrupted data and can handle partial observations.
  • Limitations with dominant sparse matrices: LMaFit fails when the sparse matrix's magnitude is much larger than the low-rank matrix's. However, simple remedial techniques (truncation or excluding entries) can alleviate this issue to some extent.

Limitations and Future Work

  • Dominant sparse matrices: The primary limitation is the difficulty in solving problems where the sparse matrix has a much larger magnitude than the low-rank matrix. While remedial techniques are proposed, they don't completely remove this limitation and can require careful parameter tuning.
  • Rank estimation: While a rank estimation technique is provided, its effectiveness depends on the existence of a clear numerical rank, which might not always be present in "approximately low-rank" matrices. This can necessitate trial-and-error for parameter selection.
  • Theoretical guarantees: The paper acknowledges the lack of established convergence theory for ALADM on non-convex problems with more than two blocks, although empirical results show strong convergence behavior. Further theoretical studies are desired.
  • Future Work: The authors suggest that better understanding of the non-convex factorization model and its theoretical properties, along with further investigation into the remedial techniques for dominant sparse matrices, would be valuable.

Summary updated

BibTeX
@article{shen2014augmented,
  author = {Y. Shen and Z. Wen and Y. Zhang},
  title = {{Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization}},
  journal = {Optim. Methods Softw},
  year = {2014},
  doi = {10.1080/10556788.2012.700713},
}
Figure