Greedy Pursuits Based Gradual Weighting Strategy for Weighted $\ell_{1}$-Minimization
Sathiya Narayanan, Sujit Kumar Sahoo, Anamitra Makur
Abstract
In Compressive Sensing (CS) of sparse signals, standard <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> minimization can be effectively replaced with Weighted <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> -minimization <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\mathbf{W}\ell_{1})$</tex> if some information about the signal or its sparsity pattern is available. If no such information is available, Re-Weighted <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> -minimization <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\mathbf{ReW}\ell_{1})$</tex> can be deployed. ReW <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell _{1}$</tex> solves a series of W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> problems, and therefore, its computational complexity is high. An alternative to ReW <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> is the Greedy Pursuits Assisted Basis Pursuit (GPABP) which employs multiple Greedy Pursuits (GPs) to obtain signal information which in turn is used to run W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> . Although GPABP is an effective fusion technique, it adapts a binary weighting strategy for running W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> , which is very restrictive. In this article, we propose a gradual weighting strategy for W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> , which handles the signal estimates resulting from multiple GPs more effectively compared to the binary weighting strategy of GPABP. The resulting algorithm is termed as Greedy Pursuits assisted Weighted <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> -minimization <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\mathbf{GP-W}\ell_{1})$</tex> . For GP-W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> , we derive the theoretical upper bound on its reconstruction error. Through simulation results, we show that the proposed GP-W <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> outperforms ReW <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell_{1}$</tex> and the state-of-the-art GPABP.
BibTeX
@inproceedings{icassp2018_greedypursuitsba,
title = {Greedy Pursuits Based Gradual Weighting Strategy for Weighted $\ell_{1}$-Minimization},
author = {Sathiya Narayanan and Sujit Kumar Sahoo and Anamitra Makur},
booktitle = {ICASSP 2018},
year = {2018}
}