# On Finite-Step Convergence of the Non-Greedy Algorithm and Proximal Alternating Minimization Method with Extrapolation for L1-Norm PCA

arXiv: https://arxiv.org/abs/2302.07712 · HTML: https://mlsanity.com/paper/2302.07712/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 35 references that are in the map.
- First posted on arXiv 15 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [Optimal Algorithms for L1-subspace Signal Processing](https://mlsanity.com/paper/1405.6785/) (2014)
- [Efficient L1-Norm Principal-Component Analysis via Bit Flipping](https://mlsanity.com/paper/1610.01959/) (2016)
- [L1-norm Tucker Tensor Decomposition](https://mlsanity.com/paper/1904.06455/) (2019)
- [Non-Greedy L21-Norm Maximization for Principal Component Analysis](https://mlsanity.com/paper/1603.08293/) (2016)
- [A Linearly Convergent Algorithm for Rotationally Invariant ℓ1-Norm Principal Component Analysis](https://mlsanity.com/paper/2210.05066/) (2022)
- [L1-norm Principal-Component Analysis of Complex Data](https://mlsanity.com/paper/1708.01249/) (2017)

## Abstract (arXiv)

The classical non-greedy algorithm (NGA) and the recently proposed proximal alternating minimization method with extrapolation (PAMe) for L1-norm PCA are revisited and their finite-step convergence are studied. It is first shown that NGA can be interpreted as a conditional subgradient or an alternating maximization method. By recognizing it as a conditional subgradient, we prove that the iterative points generated by the algorithm will be constant in finitely many steps under a certain full-rank assumption; such an assumption can be removed when the projection dimension is one. By treating the algorithm as an alternating maximization, we then prove that the objective value will be fixed after at most leftlceilfracFmaxτ0 rightrceil steps, where the stopping point satisfies certain optimality conditions. Then, a slight modification of NGA with improved convergence properties is analyzed. It is shown that the iterative points generated by the modified algorithm will not change after at most leftlceilfrac2Fmaxτ rightrceil steps; furthermore, the stopping point satisfies certain optimality conditions if the proximal parameter τ is small enough. For PAMe, it is proved that the sign variable will remain constant after finitely many steps and the algorithm can output a point satisfying certain optimality condition, if the parameters are small enough and a full rank assumption is satisfied. Moreover, if there is no proximal term on the projection matrix related subproblem, then the iterative points generated by this modified algorithm will not change after at most leftlceil frac4Fmaxτ(1-γ) rightrceil steps and the stopping point also satisfies certain optimality conditions, provided similar assumptions as those for PAMe. The full rank assumption can be removed when the projection dimension is one.