Unified Analysis of Correlation-Aware Joint Sparse Support Recovery with ℓ0-Norm Constraint

Abstract

Sparse support recovery from multiple measurement vectors is studied in this paper. Instead of using any relaxations, we impose the explicit ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> -norm constraint and propose to identify the joint sparse support in the correlation domain. We simultaneously bound the prediction and parameter estimation errors of three algorithms with and without additional ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</inf> -norm (q = 1, 2) based regularization besides the ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> -norm constraint. Our analysis is in sharp contrast to the prior random sampling based results as our measurement matrix is deterministic Fourier and available technical arguments will not apply. Moreover, the error bounds are derived without any restriction on the tuning parameters’ ranges. The numerical implementations are carried out with customized branch and bound algorithms capable of enforcing discrete constraints.