Weakly Convex Optimization for Sparse Recovery and Its Application to DirectionofArrival Estimation
稀疏恢復的弱凸優化與到達角估計的應用
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution  

Supervisors/Advisors 

Award date  29 Aug 2019 
Link(s)
Permanent Link  https://scholars.cityu.edu.hk/en/theses/theses(43d82c6613fb4ab0b95ae34485f8c0aa).html 

Other link(s)  Links 
Abstract
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 semiconvex functions and most commonly used nonconvex penalties are formed by weakly convex sparseness. In particular, several algorithms have been devised for the application of directionalofarrival (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 squaresbased estimators are highly sensitive to outliers present in the measurement vector, leading to poor recovery. In realworld 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 convexinducing penalties and lowrank matrix approximation. Two iterative algorithms are developed to construct the noisefree 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 ongrid DOA estimators will degrade due to errors caused by the mismatches. Therefore, we consider the offgrid 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 sparsityinducing penalty for offgrid 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 sparsityaware and stateoftheart offgrid schemes.
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 squaresbased estimators are highly sensitive to outliers present in the measurement vector, leading to poor recovery. In realworld 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 convexinducing penalties and lowrank matrix approximation. Two iterative algorithms are developed to construct the noisefree 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 ongrid DOA estimators will degrade due to errors caused by the mismatches. Therefore, we consider the offgrid 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 sparsityinducing penalty for offgrid 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 sparsityaware and stateoftheart offgrid schemes.