Sublinear-time algorithms recover k-sparse signals under Jacobi polynomial orthogonal transforms by reducing to 1-sparse recovery under a sparsity structure assumption.
Fast algorithms for Jacobi expansions via nonoscillatory phase functions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We describe a suite of fast algorithms for evaluating Jacobi polynomials, applying the corresponding discrete Sturm-Liouville eigentransforms and calculating Gauss-Jacobi quadrature rules. Our approach is based on the well-known fact that Jacobi's differential equation admits a nonoscillatory phase function which can be loosely approximated via an affine function over much of its domain. Our algorithms perform better than currently available methods in most respects. We illustrate this with several numerical experiments, the source code for which is publicly available.
fields
cs.DS 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Sparse Recovery for Orthogonal Polynomial Transforms
Sublinear-time algorithms recover k-sparse signals under Jacobi polynomial orthogonal transforms by reducing to 1-sparse recovery under a sparsity structure assumption.