Sampling of signals defined over the nodes of a graph is one of the crucial problems in graph signal processing, whereas in classical signal processing, sampling is a well-defined operation; when we consider a graph signal, many new challenges arise and defining an efficient sampling strategy is not straightforward. Recently, several works have addressed this problem. The most common techniques select a subset of nodes to reconstruct the entire signal. However, such methods often require the knowledge of the signal support and the computation of the sparsity basis before sampling. Instead, in this paper, we propose a new approach to this issue. We introduce a novel technique that combines localized sampling with compressed sensing. We first choose a subset of nodes and then, for each node of the subset, we compute random linear combinations of signal coefficients localized at the node itself and its neighborhood. The proposed method provides theoretical guarantees in terms of reconstruction and stability to noise for any graph and any orthonormal basis, even when the support is not known.
@cite_8 , motivated by an analogy with classical sampling, propose a sampling strategy computing measurements as the result of iterated applications of the graph shift operator (e.g., the adjacency matrix) observed at one or more nodes. This strategy can guarantee perfect reconstruction with the optimal number of measurements and does not require knowledge of the support of the signal, so it can also be used when the support is unknown. The technique is equivalent to linear sampling where the sampling matrix has a Vandermonde structure. Unfortunately, Vandermonde matrices are known to be poorly conditioned @cite_21 resulting in severe instability even for moderately-sized graphs. The analogy drawn by the authors with classical sampling does not consider that the Vandermonde structure arising in classical sampling is a unique special case that is well conditioned, as it results in the DFT @cite_21 . Moreover, the method is highly dependent on the specific nodes chosen as observation points and it is not clear how to perform the selection.
@cite_21 @cite_8
1690143098 2147276092 2108634960 2112502349
A new scheme to sample signals defined on the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Instead of using the value of the signal observed at a subset of nodes to recover the signal in the entire graph, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, critical when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise, and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. Numerical experiments illustrating the results in both synthetic and real-world graphs close the paper. Traditional sampling theories consider the problem of reconstructing an unknown signal x from a series of samples. A prevalent assumption which often guarantees recovery from the given measurements is that x lies in a known subspace. Recently, there has been growing interest in nonlinear but structured signal models, in which x lies in a union of subspaces. In this paper, we develop a general framework for robust and efficient recovery of such signals from a given set of samples. More specifically, we treat the case in which x lies in a sum of k subspaces, chosen from a larger set of m possibilities. The samples are modeled as inner products with an arbitrary set of sampling functions. To derive an efficient and robust recovery algorithm, we show that our problem can be formulated as that of recovering a block-sparse vector whose nonzero elements appear in fixed blocks. We then propose a mixed lscr2 lscr1 program for block sparse recovery. Our main result is an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal. This result relies on the notion of block restricted isometry property (RIP), which is a generalization of the standard RIP used extensively in the context of compressed sensing. Based on RIP, we also prove stability of our approach in the presence of noise and modeling errors. A special case of our framework is that of recovering multiple measurement vectors (MMV) that share a joint sparsity pattern. Adapting our results to this context leads to new MMV recovery methods as well as equivalence conditions under which the entire set can be determined efficiently. The problem of sampling signals that are not admissible within the classical Shannon framework has received much attention in the recent past. Typically, these signals have a parametric representation with a finite number of degrees of freedom per time unit. It was shown that, by choosing suitable sampling kernels, the parameters can be computed by employing high-resolution spectral estimation techniques. In this letter, we propose a simple acquisition and reconstruction method within the framework of multichannel sampling. In the proposed approach, an infinite stream of nonuniformly-spaced Dirac impulses can be sampled and accurately reconstructed provided that there is at most one Dirac impulse per sampling period. The reconstruction algorithm has a low computational complexity, and the parameters are computed on the fly. The processing delay is minimal just the sampling period. We propose sampling circuits using inexpensive passive devices such as resistors and capacitors. We also show how the approach can be extended to sample piecewise-constant signals with a minimal change in the system configuration. We provide some simulation results to confirm the theoretical findings. We consider the problem of the reconstruction of a continuous-time function f(x) spl isin H from the samples of the responses of m linear shift-invariant systems sampled at 1 m the reconstruction rate. We extend Papoulis' generalized sampling theory in two important respects. First, our class of admissible input signals (typ. H=L sub 2 ) is considerably larger than the subspace of band-limited functions. Second, we use a more general specification of the reconstruction subspace V( spl psi ), so that the output of the system can take the form of a band-limited function, a spline, or a wavelet expansion. Since we have enlarged the class of admissible input functions, we have to give up Shannon and Papoulis' principle of an exact reconstruction. Instead, we seek an approximation f spl isin V( spl psi ) that is consistent in the sense that it produces exactly the same measurements as the input of the system. This leads to a generalization of Papoulis' sampling theorem and a practical reconstruction algorithm that takes the form of a multivariate filter. In particular, we show that the corresponding system acts as a projector from H onto V( spl psi ). We then propose two complementary polyphase and modulation domain interpretations of our solution. The polyphase representation leads to a simple understanding of our reconstruction algorithm in terms of a perfect reconstruction filter bank. The modulation analysis, on the other hand, is useful in providing the connection with Papoulis' earlier results for the band-limited case. Finally, we illustrate the general applicability of our theory by presenting new examples of interlaced and derivative sampling using splines.