# On the Suboptimality of Proximal Gradient Descent for ℓ0 Sparse Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2017.

## Built on by (most cited first, 1 of 1)

- [Noisy ℓ0-Sparse Subspace Clustering on Dimensionality Reduced Data](https://mlsanity.com/paper/2206.11079/) (2022)

## Abstract (arXiv)

We study the proximal gradient descent (PGD) method for ℓ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 ℓ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 ℓ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.