Improved time bounds for near-optimal sparse Fourier representations

Keywords

Combinatorics, Fast Fourier transform, Binary logarithm, Sublinear function, Mathematics

References

• Fast algorithms for structured matrices : theory and applications : AMS-IMS-SIAM Joint Summer Research Conference on Fast Algorithms in Mathematics, Computer Science and Engineering, August 5-9, 2001, Mount Holyoke College, South Hadley, MassachusettsVadim Olshevsky — 2003
• Numerical analysis of spectral methodsDavid Gottlieb, Steven A. Orszag — 1977
• Randomized Interpolation and Approximation of Sparse PolynomialsYishay Mansour — 1992
• I and iKevin Barraclough — 2001
• CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICSDavid Gottlieb, Steven A. Orszag, Gary A. Sod — 1978
• Approximate factorizations of Fourier matrices with nonequispaced knotsArthur Nieslony, Gabriele Steidl — 2003
• Rapid Computation of the Discrete Fourier TransformChris Anderson, M. Dahleh — 1996
• On Wavelet-Based Numerical HomogenizationAlina Chertock, Doron Levy — 2005
• Fast Fourier Transforms for Nonequispaced DataA. Dutt, Vladimir Rokhlin — 1993
• Near-optimal sparse fourier representations via samplingAnna C. Gilbert, Suvajyoti Guha, Piotr Indyk — 2002
• Asymptotic analysis for periodic structuresAlain Bensoussan, J. L. Lions, George Papanicolaou — 1979
• A Multiresolution Strategy for Numerical HomogenizationM. E. Brewster, Gregory Beylkin — 1995
• Applications of Discrete and Continuous Fourier AnalysisDonald G. Watts, H.J. Weaver — 1983
• Fast, small-space algorithms for approximate histogram maintenanceAnna C. Gilbert, Sudipto Guha, Piotr Indyk — 2002
• An adaptive treecode for computing nonbonded potential energy in classical molecular systemsZhong-Hui Duan, Robert Krasny — 2001
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationEmmanuel J. Candès, Justin Romberg, Terence Tao — 2004
• Proving hard-core predicates using list decodingAdi Akavia, S. Goldwasser, Muli Safra — 2003
• Constructing Small Sets that are Uniform in Arithmetic ProgressionsAlexander Razborov, Endre Szemerédi, Avi Wigderson — 1993
• Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysisJing Zou, Anna C. Gilbert, Martin J. Strauss — 2004
• Time Series Analysis: Forecasting and ControlO. D. Anderson, George E. P. Box, Gwilym M. Jenkins — 1978

Cited by

• An Introduction To Compressive SamplingEmmanuel J. Candès, Michael B. Wakin — 2008
• Combinatorial compressive sampling with applicationsMartin J. Strauss, Jignesh M. Patel, Mark Iwen — 2008
• Efficient sparse approximation methods for medical imagingRay Maleh — 2009
• Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.Adi Akavia — 2010
• On the computational power of quantum computersMartin Schwarz — 2013
• The Dantzig selector: Statistical estimation when P is much larger than nEmmanuel J. Candès, Terence Tao — 2005
• Methods of Music Classification and TranscriptionJonathan Baker — 2012
• Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear timeMichael Kapralov — 2016
• Images compressive sensing reconstruction by inpaintingCristina Stolojescu-Crișan, Alexandru Isar — 2015
• Simple and practical algorithm for sparse Fourier transformHaitham Hassanieh, Piotr Indyk, Dina Katabi — 2012
• Colocated MIMO radars using the Sparse Fourier TransformXiaqing Valerie Yang, Bo Li, Athina P. Petropulu — 2015
• Improved Approximation Guarantees for Sublinear-Time Fourier AlgorithmsMark Iwen — 2010
• Adaptive sub-linear Fourier algorithmsLawlor, David, Yan Wang, Andrew Christlieb — 2012
• Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse RecoverySung-Hsien Hsieh, Chun-Shien Lu, Soo‐Chang Pei — 2014
• BigBand: GHz-Wide Sensing and Decoding on Commodity RadiosHaitham Hassanieh, Lixin Shi, Omid Abari — 2013
• Efficient Software Implementation of the Nearly Optimal Sparse Fast Fourier Transform for the Noisy CaseAlexander López-Parrado, Jaime Velasco-Medina — 2015
• Manifold-Based Signal Recovery and Parameter Estimation from Compressive MeasurementsMichael B. Wakin — 2010
• Sublinear Time, Approximate Model-based Sparse Recovery For AllAnastasios Kyrillidis, Volkan Cevher — 2012
• SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard TransformXiao Li, Joseph K. Bradley, Sameer Pawar — 2015
• Rapidly computing sparse Legendre expansions via sparse Fourier transformsXianfeng Hu, Mark Iwen, Hye-Jin Kim — 2015

Related papers

• ИСПОЛЬЗОВAНИЕ ПОТЕНЦИAЛA СОЦИAЛЬНЫХ ПAРТНЕРОВ В ПОДГОТОВКЕ БУДУЩИХ ПЕДAГОГОВБ.Б. Атaбекова — 2024
• Oscillatory and asymptotic behaviour of fourth order nonlinear difference equationsYan Jurang, Liu Bin — 1997
• Fourt-order nonlinear oscillations of difference equationsE. Thandapani, I. M. Arockiasamy — 2001
• 摆动并且第四份订单的 asymptotic 行为非线性的差别方程Yan, Jurang, Liu Liu — 1997
• Large solutions of coupled sublinear/superlinear elliptic equationsJesse Peterson, David N. Smith, Aihua Wood — 2010
• The formulas for the representation of functions of two variables as a difference of sublinear functionsJerzy Grzybowski, Diethard Pallaschke, Ryszard Urbański — 2018
• Pairs of positive solutions for p-Laplacian equations with sublinear and superlinear nonlinearities which do not satisfy the AR-conditionNikolaos S. Papageorgiou, Eugénio M. Rocha — 2009
• Nontrivial solutions to non-local problems with sublinear or superlinear nonlinearitiesZhiqing Han, Ye Xue — 2020
• Exact multiplicity of solutions to superlinear and sublinear problemsJunping Shi — 2002