Sparse Recovery Using the Discrete Cosine Transform

This note considers the problem of sparse recovery in Rn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}^{n}$$\end{document} from linear measurements associated with a discrete cosine transform. The main theorem shows that an s-sparse vector in Rn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}^{n}$$\end{document} can be recovered from the first 2s coefficients of its discrete cosine transform. This theorem is a real-valued analog of a result in Foucart and Rauhut (A mathematical introduction to compressive sensing, applied and numerical harmonic analysis, Birkhäuser/Springer, New York, 2013) concerned with sparse recovery in Cn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {C}}^{n}$$\end{document} based on linear measurements via the discrete Fourier transform.