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

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

摘要： 带限图信号的采样在降维、可负担的存储和流网络数据的在线处理方面具有明确的优点。 大多数现有的采样方法旨在最小化从其样本中重建原始信号时产生的误差。 这些简明的信号通常作为计算密集型线性算子（例如，图滤波器和变换）的输入。 因此，兴趣从重建信号本身转向更高效地近似预定线性算子的输出。 在这种情况下，我们提出了一种新的采样方案，该方案利用了输入的带限性和我们希望近似的变换。 我们制定了问题，以联合优化样本选择和目标线性变换的草图，这样当后者被合理地应用于采样输入信号时，结果将接近期望的输出。 这些设计是在离线状态下进行的，并提出了几种启发式（次）最优求解器以适应高维问题，尤其是在计算资源有限的情况下。 类似的采样思路在解决线性逆问题的背景下也被证明是有效的。 开发的采样加简化复杂度处理流程对于流数据特别有用，在流数据中，线性变换必须快速且反复地应用于连续的输入或响应信号。 数值测试表明，所提出的算法在从输入图像中的最少20个像素（总共784个像素）分类手写数字方面以及在准确估计在少量节点上采样的带限图信号的频率成分方面都有效。 显示英文摘要

摘要： 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 operator (e.g., graph filters and transforms). 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. These designs are carried out off line, and several heuristic (sub)optimal solvers are proposed to accommodate high-dimensional problems, especially when computational resources are at a premium. Similar sketching as sampling ideas are also shown effective in the context of linear inverse problems. 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 or response signals. Numerical tests show the effectiveness of the proposed algorithms in classifying handwritten digits from as few as 20 out of 784 pixels in the input images, as well as in accurately estimating the frequency components of bandlimited graph signals sampled at few nodes.