2019/06/21 by Matías Valdés, Valdés, Matías, Marcelo Fiori +1
Computer Science · Engineering · #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Signal Processing (eess.SP) #Sparse and Compressive Sensing Techniques #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1906.09329
openalex publication_date 2019/06/21 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
We consider an important problem in signal processing, which consists in finding the sparsest solution of a linear system Φx=b. This problem has applications in several areas, but is NP-hard in general. Usually an alternative convex problem is considered, based on minimizing the (weighted) ℓ1 norm. For this alternative to be useful, weights should be chosen as to obtain a solution of the original NP-hard problem. A well known algorithm for this is the Re-Weighted ℓ1, proposed by Candès, Wakin and Boyd. In this article we introduce a new methodology for updating the weights of a Re-Weighted ℓ1 algorithm, based on identifying these weights as Lagrange multipliers. This is then translated into an algorithm with performance comparable to the usual methodology, but allowing an interpretation of the weights as Lagrange multipliers. The methodology may also be used for a noisy linear system, obtaining in this case a Re-Weighted LASSO algorithm, with a promising performance according to the experimental results.