Efficient Signal Reconstruction for a Broad Range of Applications
Efficient Signal Reconstruction for a Broad Range of Applications
复制标题
DOI：
10.1145/3371316.3371327
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Abolfazl Asudeh;Jees Augustine;Azade Nazi;Saravanan Thirumuruganathan;Nan Zhang;Gautam Das;D. Srivastava
中科院分区：
文献类型：
--
作者：
Abolfazl Asudeh;Jees Augustine;Azade Nazi;Saravanan Thirumuruganathan;Nan Zhang;Gautam Das;D. Srivastava
信号重构问题（SRP）是一个重要的优化问题，其目标是确定欠定线性方程组AX = B的最接近给定先验的解。它在不同的领域有大量的应用，包括网络流量工程，医学图像重建，声学，天文学等等。解决SRP的最常见方法不能扩展到大问题大小。在本文中，我们提出了一个双重制定这个问题，并显示如何适应数据库技术开发的可扩展的相似性连接时，A矩阵是稀疏和二进制提供了显着的加速。对真实世界和合成数据的广泛实验表明，我们的方法比竞争方法产生了高达20倍的显着加速。
The signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an under-determined system of linear equations AX = b that is closest to a given prior. It has a substantial number of applications in diverse areas including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for solving SRP do not scale to large problem sizes. In this paper, we propose a dual formulation of this problem and show how adapting database techniques developed for scalable similarity joins provides a significant speedup when the A matrix is sparse and binary. Extensive experiments on real-world and synthetic data show that our approach produces a significant speedup of up to 20x over competing approaches.