Newton-type and Partial Gradient Thresholding Algorithms for Sparse Signal Reconstruction

Meng, Nan ORCID: 0000-0001-7232-9348 (2022). Newton-type and Partial Gradient Thresholding Algorithms for Sparse Signal Reconstruction. University of Birmingham. Ph.D.

Meng2022PhD.pdf
Text - Accepted Version
Restricted to Repository staff only until 12 May 2024.
Available under License All rights reserved.
Download (1MB) | Request a copy

Abstract

Sparse signal recovery, one of the main tasks in signal processing, can be formulated as specific sparse optimization problems. Due to the NP-hardness of such problems, fruitful methods have been proposed at the current stage of development, among which thresholding-type methods have received considerable attention due to their structural simplicity and low complexity. The key step of thresholding methods can be regarded as integrating a search direction in traditional nonlinear optimization method and a specific thresholding technique that generates sparse vectors. The primary work of the thesis is to propose several novel thresholding-type algorithms by merging some existing thresholding techniques with new search directions.
(a) We first develop the Newton-step-based hard thresholding by introducing a modified Newton-like direction to replace the steepest descent direction that appears in many hard thresholding methods in the literature. Our method is motivated by the classic optimization theory which suggests that the Newton-like method often has a numerical advantage over the classic gradient method from the perspective of local convergence.
(b) We propose the Newton-type optimal k-thresholding algorithms, motivated by the appreciable performance of Newton-type methods and the latest more powerful optimal thresholding technique which overcomes the inherent weakness of hard thresholding by simultaneously performing objective minimization and thresholding.
(c) In commonly used thresholding methods, the iterate to be thresholded is generally not sparse due to the adoption of full descent directions, thus a large number of important pieces of information are usually thrown out during the thresholding process. We thereby adopt the partial gradient direction to generate a sparser iterate and combine the more efficient optimal k-thresholding method to propose the so-called partial gradient optimal thresholding algorithms.
(d) It was known that the use of hard thresholding usually increases the objective value in the iterative process. To avoid such a potential increase of the objective value, one can develop the optimal partial gradient direction that minimizes the objective function at a current iterate, leading to the so-called optimal partial gradient hard thresholding methods.
We will show the efficiency of the proposed algorithms from a theoretical point of view. The sufficient conditions for the efficiency of our algorithms are established in terms of the restricted isometry property (RIP), which is one of the fundamental tools for analyzing compressed sensing algorithms. Empirical results show that our algorithms are stable and robust for sparse signal reconstruction and comparable to some mainstream compressed sensing algorithms.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):