Paper Info
Title
Nearly Optimal Restricted Isometry Condition for Rank Aware Order Recursive Matching Pursuit
Abstract
In this paper, we analyze the performance guarantee of the rank aware order recursive matching pursuit (RA-ORMP) algorithm in recovering a group of jointly sparse vectors. Specifically, we show that RA-ORMP accurately reconstructs any group of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r$</tex-math></inline-formula> linearly independent jointly <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> -sparse vectors, provided that the sampling matrix has unit <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell _{2}$</tex-math></inline-formula> -norm columns and satisfies the restricted isometry property (RIP) of order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K+1$</tex-math></inline-formula> with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{K+1} &lt; {\sqrt{r}} /\left({\sqrt{K+\frac{r}{4}}+\sqrt{\frac{r}{4}}}\right)$</tex-math></inline-formula> . We show the near-optimality of the proposed guarantee by providing a group of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$r$</tex-math></inline-formula> jointly <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> -sparse vectors that cannot be recovered by RA-ORMP under <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta _{K+1} \geq \sqrt{\frac{r}{K}}$</tex-math></inline-formula> . We also present a condition of RA-ORMP in the more realistic scenarios where a sampling matrix might not have unit <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell _{2}$</tex-math></inline-formula> -norm columns and the measurements are contaminated with noise.
Year
DOI
Venue
2019
10.1109/TSP.2019.2929472
IEEE Transactions on Signal Processing
Keywords
Field
DocType
Matching pursuit algorithms,Sparse matrices,Signal processing algorithms,Indexes,Image reconstruction,Noise measurement,Pollution measurement
Matching pursuit,Mathematical optimization,Combinatorics,Linear independence,Matrix (mathematics),Isometry,Performance guarantee,Sampling (statistics),Restricted isometry property,Recursion,Mathematics
Journal
Volume
Issue
ISSN
67
17
1053-587X
Citations 
PageRank 
References 
2
0.36
0
Authors
3
Name
Order
Citations
PageRank
Junhan Kim194.55
Jian Wang221613.26
Byonghyo Shim393788.51