Stochastic Recursive Gradient Support Pursuit and Its Sparse Representation Applications

Fanhua Shang, Bingkun Wei, Yuanyuan Liu, Hongying Liu, Shuang Wang, Licheng Jiao

TL;DR

This paper introduces Stochastic Recursive Gradient Support Pursuit (SRGSP), a novel algorithm for sparse representation problems that significantly reduces computational complexity by performing only one hard thresholding operation per outer iteration. SRGSP achieves a linear convergence rate and demonstrates superior performance in image denoising and face recognition tasks compared to existing state-of-the-art methods.

What Problem Does This Paper Address?

Sparse representation is a powerful technique used across various fields like signal processing, image processing, and machine learning. The core idea is to represent a high-dimensional signal as a sparse combination of a few elements from a given dictionary. This is often formulated as an $\ell_0$-norm constrained minimization problem. While many algorithms exist, including greedy methods and hard thresholding approaches, they often suffer from high per-iteration complexity, especially for large-scale and high-dimensional data. This is primarily due to the need for multiple hard thresholding operations within each iteration, which are computationally expensive. Existing stochastic methods like SG-HT and SVRGHT also face this challenge, leading to slow convergence. The paper aims to develop a more efficient algorithm that maintains or improves performance while drastically reducing computational cost.

Methods

The paper proposes a new algorithm called Stochastic Recursive Gradient Support Pursuit (SRGSP). The key innovation lies in its approach to the hard thresholding operation. Unlike previous methods that perform hard thresholding in each inner iteration, SRGSP performs it only once per outer iteration.

Here's a breakdown of the SRGSP approach:

  • Stochastic Recursive Gradient: SRGSP utilizes a stochastic recursive gradient method, which is well-suited for non-convex problems. This allows for efficient updates using mini-batches or single samples.
  • Support Identification: In each outer iteration, SRGSP first identifies a set of potentially relevant coordinates based on the current gradient and the previous support set. This combined support set is designed to be small (at most $3s$ indices, where $s$ is the sparsity level).
  • Sub-solver: Within the identified support set, SRGSP employs a sub-solver (implemented using stochastic recursive gradient descent) to find an approximate solution. This sub-solver is designed to satisfy a specific descent condition, ensuring progress towards the optimal solution.
  • Single Hard Thresholding: Crucially, after the inner iterations of the sub-solver, a single hard thresholding operation is applied to the updated estimate. This operation selects the $s$ largest magnitude coefficients, effectively enforcing sparsity.

This strategy significantly reduces the computational burden associated with hard thresholding, leading to a lower per-iteration complexity ($O(d)$ for SRGSP compared to $O(d \log d)$ for SVRGHT). The paper also provides a theoretical convergence analysis, demonstrating that SRGSP achieves a linear convergence rate.

Datasets

The paper evaluates SRGSP on both synthetic and real-world datasets:

  • Synthetic Data: Generated linear models of the form $y = Ax^* + e$, where $A$ is a matrix drawn from a Gaussian distribution, $x^*$ is a sparse vector, and $e$ is Gaussian noise. Two configurations were used:
  • $n=2500, d=5000, s^*=250$
    • $n=5000, d=10000, s^*=500$
  • Real-World Data:
    • Linear Regression: rcv1-train and real-sim datasets from the LIBSVM website. These are large-scale datasets with tens of thousands of samples and features.
  • Image Denoising: Six standard benchmark images were used, with synthetic white Gaussian noise added. An overcomplete DCT dictionary was employed.
  • Face Recognition: * Extended Yale B database: Contains 2414 frontal-face images of 38 people.
  • AR database: Contains over 4000 color images of 126 people.

Key Insights and Ideas

  • The Power of Infrequent Hard Thresholding: The most significant insight is that performing hard thresholding only once per outer iteration, rather than in every inner step, dramatically reduces computational cost without sacrificing performance. This is a key departure from many existing sparse recovery algorithms.
  • Bridging Stochasticity and Support Pursuit: SRGSP effectively combines the benefits of stochastic optimization (efficiency on large datasets) with the principles of support pursuit (identifying relevant features) in a novel way.
  • Retaining Gradient Information: By reducing the frequency of hard thresholding, SRGSP retains more of the gradient information from the intermediate steps, which can lead to better empirical performance and faster convergence.
  • Linear Convergence Guarantee: The theoretical analysis provides a strong guarantee of linear convergence, which is crucial for understanding the algorithm's scalability and reliability.

Key Results

  • Synthetic Data: SRGSP consistently converged significantly faster than baseline methods (GraSP, SG-HT, SVRGHT, LSSG-HT) in terms of both objective function values and estimation error, achieving a higher number of effective passes.
  • Real-World Data (Linear Regression): SRGSP demonstrated faster convergence rates and achieved better solutions compared to other methods, often outperforming them in much less CPU time.
  • Image Denoising: SRGSP achieved higher PSNR and SSIM values across various noise levels and datasets, outperforming OMP, GraSP, SG-HT, SVRGHT, and LSSG-HT. Visual results showed superior restoration, particularly in complex regions like the sky.
  • Face Recognition: SRGSP achieved high recognition rates on challenging datasets (AR and extended Yale B) even under significant Gaussian noise. It consistently outperformed other methods, especially as iterations increased, and was significantly faster than SVRGHT due to fewer hard thresholding operations.

Limitations and Future Work

  • Parameter Tuning: While the paper suggests empirical parameter tuning for image denoising (e.g., error bound $\epsilon \approx 1.15\sigma$), optimal parameter selection for SRGSP might still require careful consideration for different applications.
  • Dictionary Learning: For image denoising, the paper uses a fixed DCT dictionary. The authors suggest that iteratively updating the dictionary, inspired by methods like K-SVD, could further improve performance.
  • Broader Applications: The authors express interest in applying SRGSP to a wider range of sparse representation learning problems, including image super-resolution, restoration, classification, and visual tracking.
  • Extension to Other Problems: SRGSP's framework is also proposed to be extendable to low-rank matrix and tensor completion and recovery problems.

Summary updated

Abstract

In recent years, a series of matching pursuit and hard thresholding algorithms have been proposed to solve the sparse representation problem with ℓ 0 -norm constraint. In addition, some stochastic hard thresholding methods were also proposed, such as stochastic gradient hard thresholding (SG-HT) and stochastic variance reduced gradient hard thresholding (SVRGHT). However, each iteration of all the algorithms requires one hard thresholding operation, which leads to a high per-iteration complexity and slow convergence, especially for high-dimensional problems. To address this issue, we propose a new stochastic recursive gradient support pursuit (SRGSP) algorithm, in which only one hard thresholding operation is required in each outer-iteration. Thus, SRGSP has a significantly lower computational complexity than existing methods such as SG-HT and SVRGHT. Moreover, we also provide the convergence analysis of SRGSP, which shows that SRGSP attains a linear convergence rate. Our experimental results on large-scale synthetic and real-world datasets verify that SRGSP outperforms state-of-the-art related methods for tackling various sparse representation problems. Moreover, we conduct many experiments on two real-world sparse representation applications such as image denoising and face recognition, and all the results also validate that our SRGSP algorithm obtains much better performance than other sparse representation learning optimization methods in terms of PSNR and recognition rates.
BibTeX
@inproceedings{shang2020stochastic,
  author = {Fanhua Shang and Bingkun Wei and Yuanyuan Liu and Hongying Liu and Shuang Wang and Licheng Jiao},
  title = {{Stochastic Recursive Gradient Support Pursuit and Its Sparse Representation Applications}},
  booktitle = {Sensors},
  year = {2020},
  url = {https://openreview.net/forum?id=6Rd52CS3P8},
}
Figure