Rethinking sketching as sampling: A graph signal processing approach
Rethinking sketching as sampling: A graph signal processing approach
复制标题
重新思考草图作为采样：图形信号处理方法
DOI：
10.1016/j.sigpro.2019.107404
复制
发表时间：
2020
影响因子：
4.4
通讯作者：
Ribeiro, Alejandro
中科院分区：
文献类型：
--
作者：
Gama, Fernando;Marques, Antonio G.;Mateos, Gonzalo;Ribeiro, Alejandro
对属于低维子空间的信号进行采样对于降维、有限的存储器存储和流式网络数据的在线处理具有被充分记录的优点。当子空间已知时，这些信号可以被建模为带限图信号。大多数现有的采样方法被设计为最小化从其样本重构原始信号时所引起的误差。通常，这些吝啬的信号作为输入计算密集型线性算子。因此，兴趣从重建信号本身转向有效地近似规定的线性算子的输出。在这种情况下，我们提出了一种新的采样方案，利用图形信号处理，利用低维（带限）的输入结构，以及变换的输出，我们希望近似。我们制定的问题，共同优化样本选择和目标线性变换的草图，所以当后者被应用到采样的输入信号的结果是接近所需的输出。在线性反问题中，类似的草图采样思想也是有效的。因为这些设计是离线执行的，所以所得到的采样加上复杂性降低的处理流水线对于以顺序方式采集或处理的数据特别有用，其中线性算子必须快速且重复地应用于连续输入或响应信号。数值试验表明，所提出的算法的有效性，包括手写数字的分类，从少至20的784个像素的输入图像和选择传感器从网络部署进行分布式参数估计任务。
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.