Scalable Signal Reconstruction for a Broad Range of Applications.
Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas, such as network traffic engineering,...
| Publicado en: | Communications of the ACM Vol. 64; no. 2; pp. 106 - 116 |
|---|---|
| Autores principales: | , , , , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Feb2021
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=148413349&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 148413349 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Feb2021 vid: 64 iid: 2 pid: 68 pub: Association for Computing Machinery artinfo: ui: 148413349 10.1145/3441689 ppf: 106 ppct: 10 formats: tig: atl: Scalable Signal Reconstruction for a Broad Range of Applications. aug: au: Asudeh, Abolfazl Augustine, Jees Thirumuruganathan, Saravanan Nazi, Azade Zhang, Nan Das, Gautam Srivastava, Divesh su: Signal reconstruction Scalability Application software Algorithms Mathematical optimization sug: subj: Signal reconstruction Scalability Application software Algorithms Mathematical optimization ab: Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas, such as network traffic engineering, medical image reconstruction, acoustics, astronomy, and many more. Unfortunately, most of the common approaches for solving SRP do not scale to large problem sizes. We propose a novel and scalable algorithm for solving this critical problem. Specifically, we make four major contributions. First, we propose a dual formulation of the problem and develop the Direct algorithm that is significantly more efficient than the state of the art. Second, we show how adapting database techniques developed for scalable similarity joins provides a substantial speedup over Direct. Third, we describe several practical techniques that allow our algorithm to scale—on a single machine—to settings that are orders of magnitude larger than previously studied. Finally, we use the database techniques of materialization and reuse to extend our result to dynamic settings where the input to the SRP changes. Extensive experiments on realworld and synthetic data confirm the efficiency, effectiveness, and scalability of our proposal. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2021 holdings: @attributes: islocal: N |
|---|