On the Suboptimality of Proximal Gradient Descent for $\ell^{0}$ Sparse Approximation

Yingzhen Yang, Jiashi Feng, Nebojsa Jojic, Jianchao Yang, Thomas S. HuangarXiv 2017 · arXiv

Abstract

Proximal Gradient Descent (PGD) is a widely used iterative method for solving the $\ell^0$ sparse approximation problem, which is known to be NP-hard. Despite its popularity, the theoretical guarantees for PGD in this non-convex setting have been limited. This paper establishes that PGD converges to a sub-optimal solution with a bounded distance to the global optimum under conditions significantly weaker than the standard Restricted Isometry Property (RIP). Furthermore, we introduce two randomized algorithms, PGD-RMA and PGD-RDR, which reduce computational complexity while maintaining provable suboptimality bounds.

1. Introduction

The $\ell^0$ sparse approximation problem seeks the sparsest representation of a signal $y \in \mathbb{R}^d$ using a dictionary $D \in \mathbb{R}^{d \times n}$. Mathematically, this is expressed as: $$\min_{x} \|y - Dx\|_2^2 \quad \text{s.t.} \quad \|x\|_0 \leq s$$ Due to the non-convexity of the $\ell^0$ norm, this problem is computationally challenging. While convex relaxations like the $\ell^1$ norm (Lasso) are frequently employed, direct optimization using Proximal Gradient Descent (PGD) often yields superior empirical performance in machine learning and signal processing. However, PGD's convergence to local minima raises questions about its theoretical reliability. This work provides a rigorous analysis of PGD's suboptimality and proposes randomized methods to handle high-dimensional data efficiently.

2. Theoretical Guarantees for PGD

A central contribution of this work is the derivation of an $\ell^2$-distance bound between the PGD solution and the global optimum.

2.1 Beyond the Restricted Isometry Property

Traditional guarantees in sparse recovery often rely on the Restricted Isometry Property (RIP), which requires all submatrices of $D$ of a certain size to be nearly orthonormal. This paper proves that a much weaker condition suffices: the submatrix of $D$ corresponding to the union of the supports of the PGD solution and the global optimum must be non-singular. This finding significantly broadens the class of dictionaries for which PGD is theoretically sound.

2.2 Analytical Framework

To establish these bounds, the authors utilize a "capped-\ell^1" regularized problem as an analytical tool. This framework allows for a precise characterization of the gap between the local critical points reached by PGD and the true global minimizer. Additionally, the analysis shows that initializing PGD with a sparse vector (e.g., from an $\ell^1$ relaxation) ensures that the support of the iterates does not grow, facilitating faster convergence and more stable solutions.

3. Randomized Acceleration Methods

To address the $O(dn)$ complexity of the gradient step in high-dimensional settings, two randomized algorithms are proposed.

3.1 Randomized Matrix Approximation (PGD-RMA)

PGD-RMA approximates the dictionary $D$ using randomized linear algebra. By projecting $D$ into a lower-rank space ($k \ll \min(d, n)$) via a random Gaussian matrix and subsequent QR decomposition, the gradient step complexity is reduced to $O(dk + nk)$. The paper proves that the resulting solution remains close to the global optimum with high probability ($1 - 6e^{-p}$).

3.2 Randomized Dimension Reduction (PGD-RDR)

PGD-RDR applies the Johnson-Lindenstrauss lemma to reduce the dimensionality of the problem. By using a random projection matrix that preserves $\ell^2$ norms, both the signal $y$ and the dictionary $D$ are compressed to a lower dimension $m$. This reduces the gradient step complexity to $O(mn)$ while maintaining a bounded gap to the global optimum.

4. Conclusion

This research provides the first rigorous suboptimality bounds for PGD in $\ell^0$ sparse approximation under mild conditions. By demonstrating that RIP is not a prerequisite for theoretical guarantees and introducing efficient randomized variants, this work justifies the use of PGD in large-scale, non-convex optimization tasks. As this is a purely theoretical work, future research should involve empirical studies to evaluate the practical speedups offered by PGD-RMA and PGD-RDR in applications such as image denoising and dictionary learning.

Summary updated

Abstract

We study the proximal gradient descent (PGD) method for $\ell^{0}$ sparse approximation problem as well as its accelerated optimization with randomized algorithms in this paper. We first offer theoretical analysis of PGD showing the bounded gap between the sub-optimal solution by PGD and the globally optimal solution for the $\ell^{0}$ sparse approximation problem under conditions weaker than Restricted Isometry Property widely used in compressive sensing literature. Moreover, we propose randomized algorithms to accelerate the optimization by PGD using randomized low rank matrix approximation (PGD-RMA) and randomized dimension reduction (PGD-RDR). Our randomized algorithms substantially reduces the computation cost of the original PGD for the $\ell^{0}$ sparse approximation problem, and the resultant sub-optimal solution still enjoys provable suboptimality, namely, the sub-optimal solution to the reduced problem still has bounded gap to the globally optimal solution to the original problem.
BibTeX
@misc{yang2017suboptimality,
  author = {Yingzhen Yang and Jiashi Feng and Nebojsa Jojic and Jianchao Yang and Thomas S. Huang},
  title = {{On the Suboptimality of Proximal Gradient Descent for $\textbackslash\{\}ell^\{0\}$ Sparse Approximation}},
  year = {2017},
  eprint = {1709.01230},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.01230},
}
Figure