A variant of compressed sensing (Q734617)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A variant of compressed sensing |
scientific article |
Statements
A variant of compressed sensing (English)
0 references
13 October 2009
0 references
Given a bounded set \(K\) in \({\mathbb R}^n\), denote by \(L^2_K\) the set of all \(L^2-\)functions which vanish a.e. outside \(K\). Let \(\Lambda\subset{\mathbb R}^n\) be a uniformly discrete set. The following two problems are classical: \textit{Sampling Problem}: When can every function \(F\in L^2_K\) be reconstructed in a stable way from the values of its Fourier transform \(\hat F\) on \(\Lambda\)? If this is possible, \(\Lambda\) is called a set of sampling for \(L^2_K\). \textit{Interpolation Problem}: When does there exist for every sequence \(\{c(\lambda)\}\in l^2(\Lambda)\) some \(F\in L^2_K\) such that \(\hat F(\lambda)=c(\lambda),\lambda\in\Lambda\)? If this is possible, \(\Lambda\) is called a set of interpolation for \(L^2_K\). When \(K=[a,b]\subset {\mathbb R}\) is a single interval, Beurling and Kahane established that the problems can be essentially solved in terms of appropriate densities of \(\Lambda\): (i) If \(D^-(\Lambda)> b-a\) then \(\Lambda\) is a sampling set for \(L^2_{[a,b]}\). If \(D^-(\Lambda)< b-a\), then it is not. (ii) If \(D^+(\Lambda)< b-a\) then \(\Lambda\) is a set of interpolation for \(L^2_{[a,b]}\). If \(D^+(\Lambda)> b-a\), then it is not. Here \(D^\pm\) are the the upper and the lower uniform densities, respectively. \textit{H. J. Landau} [Acta Math. 117 Acta Math. 117, 37--52 (1967; Zbl 0154.15301)] discovered that the necessary conditions for sampling in (i) and interpolation in (ii) still hold in the most general situation. However, finding sufficient conditions for sampling and interpolation is a hard problem, since in general such conditions cannot be obtained in terms of densities of \(\Lambda\). This is where the geometric structure of \(\Lambda\) comes into play. \textit{A. Olevskii} and \textit{A. Ulanovskii} [C. R., Math., Acad. Sci. Paris 342, No. 12, 927--931 (2006; Zbl 1096.94017) and Geom. Funct. Anal. 18, No. 3, 1029--1052 (2008; Zbl 1169.42014)] put forward the following \textit{Universality problem}: Does there exist a set \(\Lambda\) which provides sampling/interpolation for every space \(L^2_K\) of sufficiently small/large measure? They proved that in general the answer is negative. However under some topological restrictions on \(K\) it is positive: They constructed a universal set \(\Lambda\) of given positive uniform density which provide both sampling for every compact set \(K\) in \({\mathbb R}\) satsfying meas\((K) <D(\Lambda)\) and interpolation for every open set \(K\) such that meas\((K)> D(\Lambda)\). The density of these sets \(\Lambda\) is optimal, as follows from Landau's result. The authors of the present paper suggest another very elegant construction of universal sampling/interpolation sets \(\Lambda\) of optimal density for spaces \(L^2_K\), where \(K\) is every compact/open subset of the unite square \([0,1]^2\). These sets \(\Lambda\) belong to \({\mathbb Z}^2\) and can be written explicitly. The method can be traced back to [\textit{Y. Meyer}, Nombres de Pisot, nombres de Salem et analyse harmonique. Lecture Notes in Mathematics. 117. Berlin-Heidelberg-New York: Springer-Verlag (1970; Zbl 0189.14301)]. The authors also present a result on reconstruction of positive functions and its stability and discuss sampling/interpolation in some other classical spaces of function and distributions on \([0,1]^2\). All the results are presented in the two-dimensional setting, but the same method works in any number of dimensions. The case where \(K, \Lambda\subset{\mathbb R}^n\), is treated by the authors in [C. R., Math., Acad. Sci. Paris 346, No. 23--24, 1235--1238 (2008; Zbl 1154.42006)].
0 references
Fourier expansions
0 references
compressed sensing
0 references
irregular sampling
0 references
uniform sampling and interpolation
0 references
0 references