$l_2/l_2$ guarantee on sparse Fourier transform

I am starting my studies now on signal processing, and really didn't find nothing on "$l_2/l_2$ guarantee" of a certain function, in my case:

$$||\hat{x} - \hat{x}'||_2 \leq C\text{ min }_{\text{k-sparse}\; y} ||\hat{x}-y||_2$$

My reference is "Simple and Practical Algorithm for Sparse Fourier Transform" by Hassanieh, Indyk, Katabi, Price.

What does it means to say that the function is $l_2/l_2$ guarantee or $l_{\infty}/l_2$ guarantee? A reference would be of great help!

• It's not correct to say "the function is guarantee". You can say that something satisfies a guarantee. For the $\ell_2$ and $\ell_\infty$ notation see: en.wikipedia.org/wiki/Norm_(mathematics)#p-norm – Olli Niemitalo Apr 20 '17 at 8:41
• Is the $\ell_p$ notation clear for you. Is not, I'll add details – Laurent Duval Apr 22 '17 at 13:40

A signal $s$ approximation from $x$ is often quantified by the closeness of the approximant $s'$ and the desired behavior. Traditionally, one uses norms ($\ell_p$, $p\ge 1$), pseudo-norms ($0<p < 1$) or the so-called $\ell_0$ count index. A very traditional formula uses a linear transformation $\phi$, and the approximation operator $A$, $s'=A(\phi x))$:

$$\ell_q(s -A(\phi x))\,.$$

Minimization is often looked for in specific signal classes. Looking for a $k$-sparse approximation is notoriously complicated: satisfying that $s'$ has at most $k$ nonzero components is generally NP-hard (B. K. Natarajan, Sparse Approximate Solutions to Linear Systems, 1995). So one may want a faster approximant to be bounded by a measure based on the error with the best $k$-sparse solution:

$$\ell_q(s -s')\ \le C\min_{s_k} \ell_p(s -s_k)\,,$$

where $C$ is a constant as close to $1$ as possible. Sometimes, this error is guaranteed with some probability $p$. One often finds the terms "mixed norm error guarantee".

Many references can be found in the compressed sensing literature. On of the early source is A. Cohen, W. Dahmen, and R. DeVore. Compressed Sensing and best k-term approximation, 2006. Other references include $\ell_2/\ell_2$-for each sparse recovery with low risk, A. C. Gilbert et al. You can find an $\ell_2/\ell_1$ in One sketch for all: Fast algorithms for Compressed Sensing, A. C. Gilbert, M. J. Strauss, J. A. Tropp.

A nice survey could be Sparse Recovery Using Sparse Matrices, Anna Gilbert, Piotr Indyk.

• Wow, many thanks, very complete answer! A lot more than expected :D – Gustavo Higuchi Apr 22 '17 at 16:46
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8831523656845093, "perplexity": 1116.4745084243839}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-50/segments/1606141195929.39/warc/CC-MAIN-20201128214643-20201129004643-00035.warc.gz"}