Let @math be a finite abelian group and @math be a circular convolution operator on @math . The problem under consideration is how to construct minimal @math and @math such that @math is a frame for @math , where @math is the canonical basis of @math . This problem is motivated by the spatiotemporal sampling problem in discrete spatially invariant evolution processes. We will show that the cardinality of @math should be at least equal to the largest geometric multiplicity of eigenvalues of @math , and consider the universal spatiotemporal sampling sets @math for convolution operators whose eigenvalues subject to the same largest geometric multiplicity. We will give an algebraic characterization for such sampling sets and show how this problem is linked with sparse signal processing theory and polynomial interpolation theory.
Our work is closely related to @cite_35 , in which the authors have studied the universal spatial sensor locations for discrete bandlimited space; in some sense, finding universal spatiotemporal sampling sets for convolution operators with eigenvalues subject to the same largest geometric multiplicity in our problem, is analogous to finding universal spatial sampling sets for discrete bandlimited space @math that is subject to the same cardinality of @math in @cite_35 . However, we do not make sparsity assumptions on the signal space. Instead, we seek sub-Nyquist spatial sampling rate, but want to compensate the insufficient spatial sampling rate by oversampling in time.
@cite_35
2953338282 2571527823 2133489575 2122735658
We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by KrzakalaEtAl , message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate @math exceeds the (upper) R 'enyi information dimension of the signal, @math . More precisely, for a sequence of signals of diverging dimension @math whose empirical distribution converges to @math , reconstruction is with high probability successful from @math measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension @math and @math non-zero entries, this implies reconstruction from @math measurements. For discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from @math measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal @math . We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala [30], message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of nonzero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate δ exceeds the (upper) Renyi information dimension of the signal, d(pX). More precisely, for a sequence of signals of diverging dimension n whose empirical distribution converges to pX, reconstruction is with high probability successful from d(pX) n+o(n) measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension n and k(n) nonzero entries, this implies reconstruction from k(n)+o(n) measurements. For “discrete” signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from o(n) measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal pX. Distributed sampling and reconstruction of a physical field using an array of sensors is a problem of considerable interest in environmental monitoring applications of sensor networks. Our recent work has focused on the sampling of bandlimited sensor fields. However, sensor fields are not perfectly bandlimited but typically have rapidly decaying spectra. In a classical sampling set-up it is possible to precede the A D sampling operation with an appropriate analog anti-aliasing filter. However, in the case of sensor networks, this is infeasible since sampling must precede filtering. We show that even though the effects of aliasing on the reconstruction cannot be prevented due to the "filter-less" sampling constraint, they can be suitably controlled by oversampling and carefully reconstructing the field from the samples. We show using a dither-based scheme that it is possible to estimate non-bandlimited fields with a precision that depends on how fast the spectral content of the field decays. We develop a framework for analyzing non-bandlimited fields that lead to upper bounds on the maximum pointwise error for a spatial bit rate of R bits meter. We present results for fields with exponentially decaying spectra as an illustration. In particular, we show that for fields f(t) with exponential tails; i.e., F( spl omega ) < spl pi spl alpha sup - spl alpha | spl omega | , the maximum pointwise error decays as c2e sup -a sub 1 spl radic R+ c3 1 spl radic R (e sup -2a sub 1 spl radic R) with spatial bit rate R bits meter. Finally, we show that for fields with spectra that have a finite second moment, the distortion decreases as O((1 N) sup 2 3 ) as the density of sensors, N, scales up to infinity . We show that if D is the targeted non-zero distortion, then the required (finite) rate R scales as O (1 spl radic D log 1 D). A constructive solution of the irregular sampling problem for band- limited functions is given. We show how a band-limited function can be com- pletely reconstructed from any random sampling set whose density is higher than the Nyquist rate, and give precise estimates for the speed of convergence of this iteration method. Variations of this algorithm allow for irregular sampling with derivatives, reconstruction of band-limited functions from local averages, and irregular sampling of multivariate band-limited functions. In the irregular sampling problem one is asked whether and how a band- limited function can be completely reconstructed from its irregularly sam- pled values f(xi). This has many applications in signal and image processing, seismology, meteorology, medical imaging, etc. Finding constructive solutions of this problem has received considerable attention among mathematicians and engineers. The mathematical literature provides several uniqueness results (1, 2, 17, 18, 19). It is now part of the folklore that for stable sampling the sampling rate must be at least the Nyquist rate (18). These results, as deep as they are, have had little impact for the applied sciences, because they were not constructive. If the sampling set is just a perturbation of the regular oversampling, then a reconstruction method has been obtained in a seminal paper by Duffin and Schaeffer (6) (see also (29)): if for some L > 0, a > 0, and o > 0 the sampling points xk , k e Z , satisfy (a) - ok a, k ^ I, then the norm equivalence A iR (x) ) with w < n o. This norm equivalence implies that it is possible to reconstruct through an iterative procedure, the so-called frame method. Most of the later work on constructive methods consists of variations of this method (3, 21, 22, 26). The above conditions on the sampling set exclude random irregular sampling sets, e.g., sets with regions of higher sampling density. A partial, but undesirable remedy, to handle highly irregular sampling sets, would be to force the above conditions by throwing away information on part of the points and accept a very slow convergence of the iteration.