zbMATH — the first resource for mathematics

Idempotents and compressive sampling. (Idempotents et échantillonnage parcimonieux.) (French. English summary) Zbl 1231.94044
Summary: According to E. J. Candès [“Compressive sampling”, in: M. Sanz-Solé (ed.) et al., Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 2006. Volume III: Invited lectures. Zürich: European Mathematical Society (EMS). 1433–1452 (2006; Zbl 1130.94013)] and E. J. Candès, J. Romberg and T. Tao [“Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information”, IEEE Trans. Inf. Theory 52, No. 2, 489–509 (2006; Zbl 1231.94017)], a signal is represented as a function \(x\) defined on the cyclic group \(\mathbb Z_N\). Assuming that it is carried by a set \(S\) consisting of \(T\) points, how can we reconstruct \(x\) by using only a small set \(\varOmega\) of frequencies? The procedure of Candès, Romberg and Tao is the minimal extrapolation of \(\hat x|_\varOmega\) in \(\mathbb F\ell^1\), when it exists. 1) Under which conditions can we obtain in this way all signals carried by \(T\) points? 2) Choosing \(\varOmega\) by a random selection of points in \(\mathbb Z^N\) with \(N\) very large, give an estimate of the probability that the procedure works for all signals carried by \(T\) points, 3) for all signals carried by a given set \(S\), 4) for a given signal. The answers to 1) and 2) are given with proofs and the answer to 3) without proof. Candès, Romberg and Tao answered question 4), and our answer to 3) improves their estimates. A key role is played by the idempotent \(K\) such that \(\hat K = 1_\varOmega\).

94A20 Sampling theory in information and communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Full Text: DOI
[1] Candès, Emmanuel J., Compressive sampling, () · Zbl 1130.94013
[2] Candès, Emmanuel J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE transactions on information theory, 20, 2, 489-509, (2006) · Zbl 1231.94017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.