Weakly Convex Optimization for Sparse Recovery and Its Application to Direction-of-Arrival Estimation


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date29 Aug 2019


Since the introduction of compressed sensing (CS), sparse recovery is of great interest in recent years because of its fundamental role in many signal processing areas ranging from mobile and wireless communications, acoustic tracking, parameter estimation to image processing, which is a paradigm to acquire sparse or compressible signals at a rate lower than that of the Nyquist sampling. Many techniques have been proposed to perform sparse recovery. They can be briefly classified into two categories: convex and nonconvex sparse recovery methods. In this thesis, we focus on the latter category with weakly convex penalty functions, which are also known as semi-convex functions and most commonly used nonconvex penalties are formed by weakly convex sparseness. In particular, several algorithms have been devised for the application of directional-of-arrival (DOA) estimation.

This first task of this thesis is to estimate an unknown sparse signal from a noisy underdetermined linear and inverse system, which can be formulated as an ℓ0-norm minimization with an ℓ2-norm as the metric for the residual error. In the case of the ℓ0-norm minimization, directly extending the alternating direction method of multipliers (ADMM) algorithm is not guaranteed to converge since the ℓ0-norm is highly discrete and the resulting regularization term is nonconvex. To derive a convergent algorithm for the nonconvex case, we develop a proximal ADMM algorithm via incorporating with the locally competitive algorithm, where the Nesterov acceleration is integrated for speeding up the computation process. Numerical simulations demonstrate the superiority of the proposed method over several popular sparse recovery schemes in terms of computational complexity and support recovery.

Secondly, however, it is well known that least squares-based estimators are highly sensitive to outliers present in the measurement vector, leading to poor recovery. In real-world applications, the measurement noise may be of different kinds or combinations. Impulsive noise is a typical representative which can model large errors in observations and has been widely studied in robust statistics. Hence, the ℓ2-norm data fitting model may be inefficient. By combining the concept of weak convexity with ℓ1-norm loss function, a robust sparse recovery framework for impulsive noise is proposed and theoretically analyzed. In particular, if the extended measurement matrix satisfies the restricted isometry property with a mild constant, our devised framework can robustly reconstruct the original signal.

Thirdly, application of weakly convex optimization to DOA estimation is presented by utilizing a class of weakly convex-inducing penalties and low-rank matrix approximation. Two iterative algorithms are developed to construct the noise-free data matrix, where ℓ2,1-norm is adopted as the metric for suppressing the outliers. To avoid determining the source number, the DOAs are computed via utilizing the special joint diagonalization structure of the constructed signal covariance matrix. Numerical simulations verify the direction finding performance of the proposed methods, indicating a good balance between complexity and accuracy.

Finally, the problem of DOA estimation is in a continuous range while sparse recovery is used to recover the discrete signals. Therefore, the DOAs need to be confined to the grids. If the DOAs are assumed to locate on or be close to the discrete sampling grids, sparse recovery problem can be built where the problem of DOA estimation is equivalent to find a sufficiently sparse signal with its corresponding support. In practice, however, the unknown sources are not always exactly on the discrete sampling points, and thus the performance of on-grid DOA estimators will degrade due to errors caused by the mismatches. Therefore, we consider the off-grid model via Taylor series expansion, but dictionary mismatch is introduced. The resulting problem is nonconvex with respect to the sparse signal and perturbation matrix. We develop a novel objective function regularized by the nonconvex sparsity-inducing penalty for off-grid DOA estimation, which is jointly convex with respect to the sparse signal and perturbation matrix. Then alternating minimization is applied to tackle this joint sparse representation of the signal recovery and perturbation matrix. Numerical examples are conducted to verify the effectiveness of the proposed method, which achieves more accurate DOA estimation performance and faster implementation than the conventional sparsity-aware and state-of-the-art off-grid schemes.