Sparse harmonic transforms II: best s-term approximation guarantees for bounded orthonormal product bases in sublinear-time
Tóm tắt
In this paper we develop a sublinear-time compressive sensing algorithm for approximating functions of many variables which are compressible in a given Bounded Orthonormal Product Basis (BOPB). The resulting algorithm is shown to both have an associated best s-term recovery guarantee in the given BOPB, and also to work well numerically for solving sparse approximation problems involving functions contained in the span of fairly general sets of as many as
$$\sim 10^{230}$$
orthonormal basis functions. All code is made publicly available. As part of the proof of the main recovery guarantee new variants of the well known CoSaMP algorithm are proposed which can utilize any sufficiently accurate support identification procedure satisfying a Support Identification Property (SIP) in order to obtain strong sparse approximation guarantees. These new CoSaMP variants are then proven to have both runtime and recovery error behavior which are largely determined by the associated runtime and error behavior of the chosen support identification method. The main theoretical results of the paper are then shown by developing a sublinear-time support identification algorithm for general BOPB sets which is robust to arbitrary additive errors. Using this new support identification method to create a new CoSaMP variant then results in a new robust sublinear-time compressive sensing algorithm for BOPB-compressible functions of many variables.
Tài liệu tham khảo
Adcock, B.: Infinite-dimensional \(\ell ^{1}\) minimization and function approximation from pointwise data. Constr. Approx. 45(3), 345–390 (2017)
Adcock, B., Brugiapaglia, S., Webster, C.G.: Compressed sensing approaches for polynomial approximation of high-dimensional functions. In: Compressed Sensing and Its Applications, pp. 93–124. Springer International Publishing (2017)
Bailey, J., Iwen, M.A., Spencer, C.V.: On the design of deterministic matrices for fast recovery of Fourier compressible functions. SIAM J. Matrix Anal. Appl. 33(1), 263–289 (2012)
Bittens, S., Plonka, G.: Sparse fast DCT for vectors with one-block support. Numer. Algorithms 82, 663–697 (2018)
Bittens, S., Zhang, R., Iwen, M.A.: A deterministic sparse FFT for functions with structured Fourier sparsity. Adv. Comput. Math. 45, 519–561 (2019)
Björck, A.: Numerical Methods for Least Squares Problems. Society for Industrial Applied Mathematics (SIAM), University City (1996)
Bouchot, J.-L., Rauhut, H., Schwab, C.: Multi-level Compressed Sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs. arXiv:1701.01671 (2017)
Brugiapaglia, S., Dirksen, S., Jung, H.C., Rauhut, H.: Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs, arXiv:2005.06994 (2020)
Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004)
Chkifa, A., Dexter, N., Tran, H., Webster, C.: Polynomial approximation via compressed sensing of high-dimensional functions on lower sets. Math. Comput. 87(311), 1415–1450 (2018)
Choi, B., Christlieb, A., Wang, Y.: Multi-dimensional sublinear sparse Fourier algorithm. arXiv preprint arXiv:1606.07407 (2016)
Choi, B., Christlieb, A., Wang, Y.: Multiscale high-dimensional sparse Fourier algorithms for noisy data. arXiv e-prints, arXiv:1907.03692 (2019)
Choi, B., Iwen, M., Krahmer, F.: Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables. Found. Comput. Math. (2020). https://doi.org/10.1007/s10208-020-09462-z
Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best \(k\)-term approximation. J. Am. Math. Soc. 22(1), 211–231 (2009)
Dũng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic Cross Approximation. Advanced Courses in Mathematics - CRM Barcelona. Birkhäuser, Cham (2018)
Dahlquist, G., Björck, A.: Numerical Methods in Scientific Computing, vol. 1. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2008)
DeVore, R., Petrova, G., Wojtaszczyk, P.: Approximation of functions of few variables in high dimensions. Constr. Approx. 33(1), 125–143 (2011)
Duarte, M.F., Baraniuk, R.G.: Kronecker compressive sensing. IEEE Trans. Image Process. 21(2), 494–504 (2012)
Efron, B., Stein, C.: The jackknife estimate of variance. Ann. Stat. 9(3), 586–596 (1981)
Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Springer, New York (2013)
Gilbert, A., Gu, A., Re, C., Rudra, A., Wootters, M.: Sparse recovery for orthogonal polynomial transforms. arXiv preprint arXiv:1907.08362 (2019)
Gilbert, A., Iwen, M., Strauss, M.: Empirical evaluation of a sub-linear time sparse DFT algorithm. Commun. Math. Sci. 5(4), 981–998 (2007)
Gilbert, A.C., Indyk, P., Iwen, M.A., Schmidt, L.: Recent developments in the sparse Fourier transform: a compressed Fourier transform for big data. IEEE Signal Process. Mag. 31(5), 91–100 (2014)
Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of SPIE, vol. 5914, p. 59141A (2005)
Griebel, M., Kuo, F.Y., Sloan, I.H.: The smoothing effect of the ANOVA decomposition. J. Complex. 26(5), 523–551, 2010. SI: HDA (2009)
Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1183–1194. Society for Industrial and Applied Mathematics (SIAM) (2012)
Holtz, M.: Sparse Grid Quadrature in High Dimensions With Applications in Finance and Insurance. Lecture Notes in Computational Science and Engineering, vol. 77. Springer, Berlin (2011)
Hu, X., Iwen, M., Kim, H.: Rapidly computing sparse Legendre expansions via sparse Fourier transforms. Numer. Algorithms 74(4), 1029–1059 (2017)
Iwen, M.A.: A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 20–29. Society for Industrial and Applied Mathematics (SIAM) (2008)
Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10(3), 303–338 (2010)
Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmonic Anal. 34(1), 57–82 (2013)
Kämmerer, L., Potts, D., Volkmer, T.: High-dimensional sparse FFT based on sampling along multiple rank-1 lattices. arXiv preprint arXiv:1711.05152, (2017)
Kapralov, M.: Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 264–277. ACM Press (2016)
Kapralov, M., Velingker, A., Zandieh, A.: Dimension-independent sparse Fourier transform. arXiv e-prints, arXiv:1902.10633 (2019)
Kuo, F.Y., Sloan, I.H., Wasilkowski, G.W., Woźniakowski, H.: On decomposition of multivariate functions. Math. Comput. 79(270), 953–966 (2010)
Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP ’92, pp. 261–272, London, UK. Springer (1992)
Merhi, S., Zhang, R., Iwen, M.A., Christlieb, A.: A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees. J. Fourier Anal. Appl. 25(3), 751–784 (2019)
Morotti, L.: Explicit universal sampling sets in finite vector spaces. Appl. Comput. Harmonic Anal. 43(2), 354–369 (2017)
Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmonic Anal. 26(3), 301–321 (2009)
Novak, E., Woźniakowski, H.: Tractability of multivariate problems. Volume 1: Linear information, volume 6 of EMS Tracts in Mathematics. European Mathematical Society (2008)
Potts, D., Schmischke, M.: Approximation of high-dimensional periodic functions with Fourier-based methods. arXiv preprint arXiv:1907.11412 (2019)
Potts, D., Schmischke, M.: Learning multivariate functions with low-dimensional structures using polynomial bases. arXiv preprint arXiv:1912.03195 (2019)
Potts, D., Volkmer, T.: Sparse high-dimensional FFT based on rank-1 lattice sampling. Appl. Comput. Harmonic Anal. 41(3), 713–748 (2016)
Potts, D., Volkmer, T.: Multivariate sparse FFT based on rank-1 Chebyshev lattice sampling. In: 2017 International Conference on Sampling Theory and Applications (SampTA), pp. 504–508. IEEE (2017)
Rauhut, H.: Random sampling of sparse trigonometric polynomials. Appl. Comput. Harmonic Anal. 22(1), 16–42 (2007)
Rauhut, H., Ward, R.: Sparse Legendre expansions via \(\ell _1\)-minimization. J. Approx. Theory 164(5), 517–533 (2012)
Schwab, C., Todor, R.A.: Karhunen–Loève approximation of random fields by generalized fast multipole methods. J. Comput. Phys. 217(1), 100–122 (2006)
Segal, B., Iwen, M.A.: Improved sparse Fourier approximation results: faster implementations and stronger guarantees. Numer. Algorithms 63(2), 239–263 (2013)
Shen, J., Wang, L.-L.: Sparse spectral approximations of high-dimensional problems based on hyperbolic cross. SIAM J. Numer. Anal. 48(3), 1087–1109 (2010)