Many problems in machine learning and signal processing involve decomposing a large, messy matrix into simpler, structured components. We might want to separate a static background from moving objects in a video, or compress a massive neural network into a compact form. While these problems are often mathematically "non-convex"—meaning they are difficult to solve globally—a powerful and intuitive strategy has emerged: alternating minimization.
The core intuition is simple: if you have a problem with two unknown parts, fix the first part and solve for the second; then fix the second and solve for the first. By repeating this "coordinate descent" process, complex global optimizations become a sequence of manageable, often closed-form steps.
The Mechanics of Iterative Refinement
The most common application of this idea is decomposing a matrix $M$ into two factors, $U$ and $V$, such that $M \approx UV^T$. In its simplest form, as explored by Liu et al. for rank-one matrix completion, the algorithm alternates between optimizing two vectors whose outer product approximates the target. By holding one vector constant, the update for the other becomes a straightforward linear problem.
This principle extends to more complex structures. For example, in Quadratic Matrix Factorization (QMF), Chen et al. and Sun use alternating minimization to capture curved data manifolds. They iteratively refine estimates for quadratic function parameters and latent variables, leveraging the fact that each sub-problem can be treated as a specialized projection or regression.
Separating Low-Rank and Sparse Components
A recurring theme in this research direction is the decomposition of a matrix into a low-rank component (representing global structure) and a sparse component (representing outliers or localized features). This is the foundation of Robust Principal Component Analysis (RPCA).
Zhou et al. introduced GoDec, which solves this by alternating between two specific constraints:
- Rank Constraint: Use Singular Value Decomposition (SVD) to find the best low-rank approximation.
- Sparse Constraint: Use hard-thresholding to pick the most significant entries for the sparse component.
Similarly, Netrapalli et al. proposed AltProj, which treats the problem as alternating projections onto the sets of low-rank and sparse matrices. This approach avoids the slow computational overhead of traditional convex relaxations while maintaining rigorous theoretical guarantees.
This "Low-Rank + Sparse" framework has recently moved into the heart of Deep Learning. To compress Large Language Models (LLMs), Makni et al. developed the HASSLE-free framework, which uses alternating minimization to split weight matrices into sparse and low-rank parts. Zhang et al. followed a similar path with OATS, specifically using this decomposition to protect "outlier features" that are critical for model accuracy during pruning.
Greedy Atoms and Submatrix Localization
Sometimes, rather than solving for the whole matrix at once, it is more efficient to find the best "rank-one" piece and subtract it, repeating the process greedily.
Ghodsi et al. proposed R1D for Nonnegative Matrix Factorization, which extracts rank-one submatrices one at a time. The algorithm alternates between optimizing row indices and column indices to find the dominant "singular triple" of a specific data subset. This same logic is used by Shen et al. in their Optimal Atom strategy for matrix completion. Instead of a full SVD, they use alternating minimization to find the single best direction to fit the current residual, significantly speeding up convergence on massive datasets.
This row-column alternating refinement is also the key to finding "needles in haystacks." Liu et al. use it for submatrix localization, alternating between selecting the best rows for a fixed set of columns and vice versa to identify high-value blocks in noisy data. In the realm of big data, Cortinovis et al. use a similar refinement loop to select the most informative subset of rows and columns, allowing for sublinear-time matrix approximations.
Why It Works: From Convexity to Practicality
Historically, researchers favored "convex relaxations" of these problems because they offered global optimality guarantees. However, as Wang et al. argue with their PARSuMi algorithm, these relaxations often struggle with real-world noise and massive scales.
Alternating minimization works because it directly tackles the non-convex constraints (like exact rank or exact sparsity). While the joint problem is difficult, the individual sub-problems are often "nice." For instance, in the work of Huang et al. on sensor detection, the low-rank update has a closed-form solution, while the sparse update is a standard quadratic program.
By breaking the entanglement between different structural constraints, alternating minimization provides a path that is both computationally efficient and surprisingly robust, whether the goal is identifying cancer subtypes Yu et al. or uncovering the pre-fine-tuning weights of a generative model Horwitz et al..
Key Foundational Work
A general model for clustering binary data (2005) — contributed 1 concept elements to this direction.
Nonnegative matrix factorization via rank-one downdate (2008) — contributed 1 concept elements to this direction.