Rethinking sketching as sampling: Linear transforms of graph signals
Fernando Gama, Antonio Garcia Marques, Gonzalo Mateos, Alejandro Ribeiro · 2016
Sampling of bandlimited graph signals has well-documented merits for dimensionality reduction, affordable storage, and online processing of streaming network data. Most existing sampling methods are designed to minimize the error incurred when reconstructing the original signal from its samples. Oftentimes these parsimonious signals serve as inputs to computationally-intensive linear transformations (e.g., graph filters). Hence, interest shifts from reconstructing the signal itself towards instead approximating the output of the prescribed linear operator efficiently. In this context, we propose a novel sampling scheme that leverages the bandlimitedness of 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 the target linear transformation, so when the latter is affordably applied to the sampled input signal the result is close to the desired output. The developed sampling plus reduced-complexity processing pipeline is particularly useful for streaming data, where the linear transform has to be applied fast and repeatedly to successive inputs.