Sampling of bandlimited graph signals has well-documented merits fordimensionality reduction, affordable storage, and online processing ofstreaming network data. Most existing sampling methods are designed to minimizethe error incurred when reconstructing the original signal from its samples.Oftentimes these parsimonious signals serve as inputs tocomputationally-intensive linear operator (e.g., graph filters and transforms).Hence, interest shifts from reconstructing the signal itself towards insteadapproximating the output of the prescribed linear operator efficiently. In thiscontext, we propose a novel sampling scheme that leverages the bandlimitednessof the input as well as the transformation whose output we wish to approximate.We formulate problems to jointly optimize sample selection and a sketch of thetarget linear transformation, so when the latter is affordably applied to thesampled input signal the result is close to the desired output. These designsare carried out off line, and several heuristic (sub)optimal solvers areproposed to accommodate high-dimensional problems, especially whencomputational resources are at a premium. Similar sketching as sampling ideasare also shown effective in the context of linear inverse problems. Thedeveloped sampling plus reduced-complexity processing pipeline is particularlyuseful for streaming data, where the linear transform has to be applied fastand repeatedly to successive inputs or response signals. Numerical tests showthe effectiveness of the proposed algorithms in classifying handwritten digitsfrom as few as 20 out of 784 pixels in the input images, as well as inaccurately estimating the frequency components of bandlimited graph signalssampled at few nodes.
展开▼
