2017/11/14 by Lutz Kämmerer, Daniel Potts, Kämmerer, Lutz +3 · 1 citation
Computer Science · Engineering · Mathematics · #42A10 #65T #65T40 #FOS: Mathematics #Image and Signal Denoising Methods #Mathematical Analysis and Transform Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1711.05152
openalex publication_date 2017/11/14 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
The reconstruction of high-dimensional sparse signals is a challenging task\nin a wide range of applications. In order to deal with high-dimensional\nproblems, efficient sparse fast Fourier transform algorithms are essential\ntools. The second and third authors have recently proposed a\ndimension-incremental approach, which only scales almost linear in the number\nof required sampling values and almost quadratic in the arithmetic complexity\nwith respect to the spatial dimension d. Using reconstructing rank-1 lattices\nas sampling scheme, the method showed reliable reconstruction results in\nnumerical tests but suffers from relatively large numbers of samples and\narithmetic operations. Combining the preferable properties of reconstructing\nrank-1 lattices with small sample and arithmetic complexities, the first author\ndeveloped the concept of multiple rank-1 lattices. In this paper, both concepts\n- dimension-incremental reconstruction and multiple rank-1 lattices - are\ncoupled, which yields a distinctly improved high-dimensional sparse fast\nFourier transform. Moreover, the resulting algorithm is analyzed in detail with\nrespect to success probability, number of required samples, and arithmetic\ncomplexity. In comparison to single rank-1 lattices, the utilization of\nmultiple rank-1 lattices results in a reduction in the complexities by an\nalmost linear factor with respect to the sparsity. Various numerical tests\nconfirm the theoretical results, the high performance, and the reliability of\nthe proposed method.\n