Efficient LED-SAC sparse estimator using fast sequential adaptive coordinate-wise optimization (LED-2SAC) (Q1718121)

Summary: Solving the underdetermined system of linear equations is of great interest in signal processing application, particularly when the underlying signal to be estimated is sparse. Recently, a new sparsity encouraging penalty function is introduced as Linearized Exponentially Decaying penalty, LED, which results in the sparsest solution for an underdetermined system of equations subject to the minimization of the least squares loss function. A sequential solution is available for LED-based objective function, which is denoted by LED-SAC algorithm. This solution, which aims to sequentially solve the LED-based objective function, ignores the sparsity of the solution. In this paper, we present a new sparse solution. The new method benefits from the sparsity of the signal both in the optimization criterion (LED) and its solution path, denoted by Sparse SAC (2SAC). The new reconstruction method denoted by LED-2SAC (LED-Sparse SAC) is consequently more efficient and considerably fast compared to the LED-SAC algorithm, in terms of adaptability and convergence rate. In addition, the computational complexity of both LED-SAC and LED-2SAC is shown to be of order \(\mathcal{O} \left(d^2\right)\), which is better than the other batch solutions like LARS. LARS algorithm has complexity of order \(\mathcal{O} \left(d^3 + n d^2\right)\), where \(d\) is the dimension of the sparse signal and \(n\) is the number of observations.