标题： 重新思考草图作为抽样：一种图信号处理方法 显示英文标题

标题： Rethinking Sketching as Sampling: A Graph Signal Processing Approach

摘要： 信号属于低维子空间的采样在降维、有限内存存储和流式网络数据的在线处理方面具有明确的优势。当子空间已知时，这些信号可以建模为带限图信号。大多数现有的采样方法旨在最小化从其样本重建原始信号时产生的误差。这些稀疏信号通常作为计算密集型线性算子的输入。因此，研究兴趣从重建信号本身转向高效地近似指定线性算子的输出。在此背景下，我们提出了一种新的采样方案，利用图信号处理，利用输入的低维（带限）结构以及我们希望近似的变换。我们制定了问题，以联合优化样本选择和目标线性变换的草图，以便当后者应用于采样的输入信号时，结果接近期望的输出。类似的草图和采样思想在在线性逆问题的背景下也被证明是有效的。由于这些设计是在离线进行的，因此生成的采样加上简化复杂度的处理流程对于按顺序获取或处理的数据特别有用，在这种情况下，必须快速且重复地将线性算子应用于连续的输入或响应信号。显示所提算法有效性的数值测试包括从输入图像中仅784个像素中的20个像素对手写数字进行分类，以及从执行分布式参数估计任务的网络中选择传感器。 显示英文摘要

摘要： Sampling of signals belonging to a low-dimensional subspace has well-documented merits for dimensionality reduction, limited memory storage, and online processing of streaming network data. When the subspace is known, these signals can be modeled as bandlimited graph signals. 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 operators. Hence, interest shifts from reconstructing the signal itself towards approximating the output of the prescribed linear operator efficiently. In this context, we propose a novel sampling scheme that leverages graph signal processing, exploiting the low-dimensional (bandlimited) structure 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 applied to the sampled input signal the result is close to the desired output. Similar sketching as sampling ideas are also shown effective in the context of linear inverse problems. Because these designs are carried out off line, the resulting sampling plus reduced-complexity processing pipeline is particularly useful for data that are acquired or processed in a sequential fashion, where the linear operator has to be applied fast and repeatedly to successive inputs or response signals. Numerical tests showing the effectiveness of the proposed algorithms include classification of handwritten digits from as few as 20 out of 784 pixels in the input images and selection of sensors from a network deployed to carry out a distributed parameter estimation task.