pith. sign in

arxiv: 1907.08362 · v1 · pith:YD6B3ZM6new · submitted 2019-07-19 · 💻 cs.DS

Sparse Recovery for Orthogonal Polynomial Transforms

Anna Gilbert , Albert Gu , Christopher Re , Atri Rudra , Mary Wootters This is my paper

Pith reviewed 2026-05-24 19:16 UTC · model grok-4.3

classification 💻 cs.DS
keywords sparse recoveryorthogonal polynomial transformsJacobi polynomialssublinear algorithmssparse FFTChebyshev polynomialsLegendre polynomialssignal processing
0
0 comments X

The pith

The paper gives sublinear-time algorithms for sparse recovery under any orthogonal transform derived from Jacobi polynomials.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes sublinear algorithms that recover a k-sparse vector after it has been transformed by any orthogonal polynomial transform coming from Jacobi polynomials, running in time polynomial in k and the logarithm of the dimension. This extends the well-known sparse FFT results, which handle only the discrete Fourier transform, to a much larger family of transforms that appear in numerical analysis and signal processing. The method first reduces the general k-sparse recovery task to the 1-sparse case for any flat orthogonal polynomial transform, then solves the resulting 1-sparse instance specifically for Jacobi-derived transforms. A reader would care because the same transforms underlie many practical computations where fast sparse recovery has previously been unavailable.

Core claim

We give sublinear-time algorithms---running in time poly(k log N)---for solving the sparse recovery problem for any orthogonal polynomial transform F derived from Jacobi polynomials, by first reducing the k-sparse problem to the 1-sparse problem for any flat orthogonal polynomial transform and then solving the 1-sparse instance for the Jacobi case.

What carries the argument

A general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform.

If this is right

  • The result covers Chebyshev and Legendre transforms as special cases of Jacobi polynomials.
  • Vectors whose support is chosen uniformly at random satisfy the needed structural property with high probability.
  • The same reduction applies to any flat orthogonal polynomial transform, not just those from Jacobi polynomials.
  • Recovery succeeds in an l2 sense and works for both exactly k-sparse and nearly k-sparse vectors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The reduction technique could be tested on other families of orthogonal polynomials to see whether it yields sublinear algorithms beyond the Jacobi case.
  • Practical implementations for specific parameter choices of Jacobi polynomials would reveal whether the poly(k log N) bound is achievable in code.
  • If the structural assumption on support can be relaxed or removed, the method would apply to arbitrary sparse vectors without probability caveats.

Load-bearing premise

The sparse vector must satisfy an assumption on the structure of its support.

What would settle it

Construct a k-sparse input vector whose support violates the required structural property, run the algorithm, and check whether recovery fails while still using only poly(k log N) queries.

Figures

Figures reproduced from arXiv: 1907.08362 by Albert Gu, Anna Gilbert, Atri Rudra, Christopher Re, Mary Wootters.

Figure 1
Figure 1. Figure 1: A (cartoon of a) (d, ǫ, θ, γ)-box car polynomial. (i) With probability at least C0γ/2, we have θh ∈ h θℓ − γ 4 , θℓ + γ 4 i , (12) and (ii) Conditioned on (12), the following holds with probability 1: {θi |i ∈ H \ {h}} ∩ h θℓ − γ 2 , θℓ + γ 2 i = ∅. (13) Proof. We start with part (i). Indeed note that for (12) to occur, we must have θℓ ∈ h θh − γ 4 , θh + γ 4 i . Since the orthogonal polynomial family is (… view at source ↗
Figure 2
Figure 2. Figure 2: The intuition behind the Peeler algorithm (Alg. 2). The boxcar polynomial bℓ (hopefully) isolates a single spike in xˆ − ˆz, resulting in yˆℓ ≈ yℓeh. Each entry of F−1yˆ can be queried by querying O(d) entries of x − z, using the SimulateQueryAccess algorithm (Alg. 4). Using this access, we can use the 1-sparse recovery algorithm on F −1yˆ to recover yℓ and eh. Then we add this spike to zˆ and continue. 17… view at source ↗
Figure 3
Figure 3. Figure 3: The set-up for the proof of Lemma 4.11. The contribution to qˆ from within R\{h} comes only from wˆ , and is pointwise multiplied by a boxcar polynomial bℓ with value at most 1 + ǫ/√ k. The contribution to qˆ from outside of R comes from both wˆ and xˆ, but is pointwise multiplied by a boxcar polynomial with value at most ǫ/√ k. Recalling that ˆr = vˆ − ˆz, we can bound the noise qˆ by kqˆk 2 2 = kDbℓ · ˆr… view at source ↗
Figure 4
Figure 4. Figure 4: The set-up for the proof of Lemma 4.12. The contribution to qˆ from within R \ {h, h′} comes only from wˆ , and is pointwise multiplied by a boxcar polynomial bℓ with value at most 1 + ǫ/√ k. The contribution to qˆ from outside of R comes from both wˆ and xˆ, but is pointwise multiplied by a boxcar polynomial with value at most ǫ/√ k. Notice that h ′ might be ⊥, in which case the picture looks similar to … view at source ↗
read the original abstract

In this paper we consider the following sparse recovery problem. We have query access to a vector $\vx \in \R^N$ such that $\vhx = \vF \vx$ is $k$-sparse (or nearly $k$-sparse) for some orthogonal transform $\vF$. The goal is to output an approximation (in an $\ell_2$ sense) to $\vhx$ in sublinear time. This problem has been well-studied in the special case that $\vF$ is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time $O(k \cdot \mathrm{polylog} N)$. However, for transforms $\vF$ other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms---running in time $\poly(k \log(N))$---for solving the sparse recovery problem for orthogonal transforms $\vF$ that arise from orthogonal polynomials. More precisely, our algorithm works for any $\vF$ that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the $k$-sparse sparse recovery problem to the $1$-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims sublinear-time algorithms running in poly(k log N) time for sparse recovery under orthogonal transforms F derived from Jacobi polynomials (including Chebyshev and Legendre as special cases). It reduces the k-sparse (or nearly k-sparse) recovery problem to the 1-sparse case for any 'flat' orthogonal polynomial transform, then solves the 1-sparse case specifically for Jacobi-derived transforms. The result requires an assumption on the sparsity structure of the input vector (satisfied w.h.p. by random supports).

Significance. If the reduction and 1-sparse solver are rigorous and the poly(k log N) bound holds without hidden dependence on the assumption, the work would extend sparse FFT techniques beyond DFT/DCT to a broad class of transforms arising in numerical analysis and signal processing. The general reduction for flat transforms would be a reusable contribution.

major comments (2)
  1. [Abstract] Abstract and approach description: the assumption on sparsity structure is load-bearing for the central poly(k log N) claim, as the reduction from k-sparse to 1-sparse is stated to require it and the guarantee therefore does not apply to arbitrary supports (unlike standard sparse FFT results for the DFT). The exact formal statement of the assumption, where it is used in the reduction, and whether the runtime remains sublinear when the assumption fails must be specified.
  2. [Approach description] Approach description: the reduction is presented as holding for any flat orthogonal polynomial transform, yet the abstract provides only a high-level description with no error analysis, proof sketch, or verification that the composed algorithm achieves poly(k log N) time; without these details the soundness of the runtime bound cannot be assessed.
minor comments (1)
  1. [Abstract] Clarify the precise approximation guarantee (ℓ2 sense) for the nearly k-sparse case and how it interacts with the sparsity-structure assumption.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on clarifying the role of the sparsity assumption and strengthening the high-level description of the approach. We address the comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and approach description: the assumption on sparsity structure is load-bearing for the central poly(k log N) claim, as the reduction from k-sparse to 1-sparse is stated to require it and the guarantee therefore does not apply to arbitrary supports (unlike standard sparse FFT results for the DFT). The exact formal statement of the assumption, where it is used in the reduction, and whether the runtime remains sublinear when the assumption fails must be specified.

    Authors: We agree that the sparsity structure assumption is essential to the reduction and the claimed runtime. The assumption (formalized as the support being 'flat' with respect to the orthogonal polynomial basis, see Definition 2.1) is required for the k-sparse to 1-sparse reduction in Theorem 3.1 and is used throughout Section 3. The sublinear runtime guarantee does not hold for arbitrary supports that violate the assumption. We will revise the abstract to state the assumption formally, indicate its use in the reduction, and explicitly note that the poly(k log N) bound applies only when the assumption holds (while random supports satisfy it w.h.p., as already mentioned). revision: yes

  2. Referee: [Approach description] Approach description: the reduction is presented as holding for any flat orthogonal polynomial transform, yet the abstract provides only a high-level description with no error analysis, proof sketch, or verification that the composed algorithm achieves poly(k log N) time; without these details the soundness of the runtime bound cannot be assessed.

    Authors: The full manuscript provides the reduction for any flat orthogonal polynomial transform in Section 3 (including error analysis via the flatness property) and composes it with the Jacobi-specific 1-sparse solver in Section 4 to obtain the poly(k log N) bound. To address the concern about the abstract, we will add a concise proof sketch and reference to the key runtime theorem (Theorem 4.3) in the introduction, along with a brief mention of the error propagation in the abstract. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is constructive and self-contained

full rationale

The paper explicitly states an assumption on sparsity structure (random supports satisfy it w.h.p.) and presents a general reduction from k-sparse to 1-sparse recovery for any flat orthogonal polynomial transform, followed by a specific 1-sparse solver for Jacobi polynomials. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work appear. The result is an algorithmic construction with stated limitations, not a closed loop reducing to its own inputs by definition. This matches the default case of a non-circular paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review limits visibility into parameters or entities. No free parameters or invented entities are mentioned. The work rests on standard properties of orthogonal polynomials.

axioms (1)
  • domain assumption Orthogonal polynomial transforms derived from Jacobi polynomials admit a flatness property enabling reduction from k-sparse to 1-sparse recovery
    Invoked to justify the general reduction step described in the abstract.

pith-pipeline@v0.9.0 · 5867 in / 1126 out tokens · 25269 ms · 2026-05-24T19:16:46.201465+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 2 internal anchors

  1. [1]

    https://en.wikipedia.org/wiki/Jacobi_polynomials#Differential_equation

    work page

  2. [2]

    http://www.chebfun.org

    work page

  3. [3]

    arXiv 1903.12135 (2019)

    B/suppress lasiok, J., Lopatto, P., Luh, K., and Marcinek, J.Sparse Reconstruction from Hadamard Matrices: A Lower Bound. arXiv 1903.12135 (2019)

    work page arXiv 1903

  4. [4]

    An Improved Estimate in the Restricted Isometry Problem

    Bourgain, J. An Improved Estimate in the Restricted Isometry Problem . Springer International Publishing, Cham, 2014, pp. 65–70

    work page 2014

  5. [5]

    Fast Algorithms for the Multi-dimensional Jacobi Polynomial Transform

    Bremer, J., Pang, Q., and Yang, H. Fast Algorithms for the Multi-dimensional Jacobi Polynomial Transform. arXiv e-prints (Jan 2019), arXiv:1901.07275

    work page arXiv 2019

  6. [6]

    Fast algorithms for Jacobi expansions via nonoscillatory phase functions

    Bremer, J., and Yang, H. Fast algorithms for Jacobi expansions via nonoscillatory phase fun ctions. arXiv e-prints (Mar 2018), arXiv:1803.03889

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  7. [7]

    Sparse Harmonic Transforms: A New Class of Sublinear-time Algorithms for Learning Functions of Many Variables

    Choi, B., Iwen, M., and Krahmer, F. Sparse Harmonic Transforms: A New Class of Sublinear-time Algorithms for Learning Functions of Many Variables. arXiv 1808.04932 (2018)

    work page arXiv 2018

  8. [8]

    Cook, J. D. Orthogonal polynomials and gaussian quadrature. https://www.johndcook.com/OrthogonalPolynomials.pdf. 15This assumes computing the arccos values takes O(1) time. 49

    work page

  9. [9]

    M., and R ´ e, C

    Dao, T., De Sa, C. M., and R ´ e, C. Gaussian quadrature for kernel features. In Advances in Neural Information Processing Systems 30 , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Curran Associates, Inc., 2017, pp. 6107–6117

    work page 2017

  10. [10]

    R., Healy, Jr., D

    Driscoll, J. R., Healy, Jr., D. M., and Rockmore, D. N. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. 26 , 4 (Aug. 1997), 1066–1099

    work page 1997

  11. [11]

    A Mathematical Introduction to Compressive Sensing

    Foucart, S., and Rauhut, H. A Mathematical Introduction to Compressive Sensing . Springer Science & Business Media, August 2013

    work page 2013

  12. [12]

    C., Guha, S., Indyk, P., Muthukrishnan, S., and S trauss, M

    Gilbert, A. C., Guha, S., Indyk, P., Muthukrishnan, S., and S trauss, M. Near-optimal sparse fourier representations via sampling. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing (New York, NY, USA, 2002), STOC ’02, ACM, pp. 152–161

    work page 2002

  13. [13]

    C., Indyk, P., Iwen, M., and Schmidt, L

    Gilbert, A. C., Indyk, P., Iwen, M., and Schmidt, L. Recent Developments in the Sparse Fourier Transform. IEEE Signal Processing Magazine (2014)

    work page 2014

  14. [14]

    Nearly optimal sparse fourier transform

    Hassanieh, H., Indyk, P., Katabi, D., and Price, E. Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on The ory of computing (2012), ACM, pp. 563– 578

    work page 2012

  15. [15]

    Rapidly computing sparse legendre expansions via sparse fourier transforms

    Hu, X., Iwen, M., and Kim, H. Rapidly computing sparse legendre expansions via sparse fourier transforms. Numerical Algorithms 74 , 4 (2017)

    work page 2017

  16. [16]

    Hua, Y., and Sarkar, T. K. Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise. IEEE Transactions on Acoustics, Speech, and Signal Process ing 38, 5 (May 1990), 814–824

    work page 1990

  17. [17]

    Sample-optimal fourier sampling in any constant dimension

    Indyk, P., and Kapralov, M. Sample-optimal fourier sampling in any constant dimension. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Scien ce (2014), IEEE, pp. 514–523

    work page 2014

  18. [18]

    (nearly) sample-optimal sparse fourier transform

    Indyk, P., Kapralov, M., and Price, E. (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fifth annual ACM-SIAM symposium o n Discrete algorithms (2014), Society for Industrial and Applied Mathematics, pp. 480–499

    work page 2014

  19. [19]

    Ismail, M. E. H., and Muldoon, M. E. Bounds for the small real and purely imaginary zeros of bessel and related functions. Methods and Applications of Analysis 2 , 1 (1995)

    work page 1995

  20. [20]

    Dimension-independent sparse fourier transform

    Kapralov, M., Velingker, A., and Zandieh, A. Dimension-independent sparse fourier transform. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on D iscrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (2019), pp. 2709–2728

    work page 2019

  21. [21]

    Chebyshev polynomials in tcs and algorithm design.http://www.cameronmusco.com/personal_site/pdfs/retreatTalk.pdf

    Musco, C. Chebyshev polynomials in tcs and algorithm design.http://www.cameronmusco.com/personal_site/pdfs/retreatTalk.pdf

    work page

  22. [22]

    A generalized prony method for reconstruction of sparse sums of eigenfunctions of linear operators

    Peter, T., and Plonka, G. A generalized prony method for reconstruction of sparse sums of eigenfunctions of linear operators. Inverse Problems 29 , 2 (jan 2013), 025001

    work page 2013

  23. [23]

    Parameter estimation for exponential sums by approximate prony method

    Potts, D., and Tasche, M. Parameter estimation for exponential sums by approximate prony method. Signal Processing 90 , 5 (2010), 1631 – 1642. Special Section on Statistical Signal and A rray Processing

    work page 2010

  24. [24]

    Reconstruction of sparse legendre and gegenbauer expansions

    Potts, D., and Tasche, M. Reconstruction of sparse legendre and gegenbauer expansions. BIT Numerical Mathematics 56 , 3 (2016), 1019–1043

    work page 2016

  25. [25]

    Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

    Rao, S. Improved Lower Bounds for the Restricted Isometry Property o f Subsampled Fourier Matrices. arXiv 1903.12146 (2019). 50

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  26. [26]

    Sparse legendre expansions via ℓ1-minimization

    Rauhut, H., and W ard, R. Sparse legendre expansions via ℓ1-minimization. J. Approx. Theory 164 , 5 (May 2012), 517–533

    work page 2012

  27. [27]

    An Introduction to the Approximation of Functions

    Rivlin, T. An Introduction to the Approximation of Functions . Blaisdell book in numerical analysis and computer science. Dover Publications, 1981

    work page 1981

  28. [28]

    On sparse reconstruction from fourier and gaussian measure- ments

    Rudelson, M., and Vershynin, R. On sparse reconstruction from fourier and gaussian measure- ments. Communications on Pure and Applied Mathematics 61 , 8 (2008), 1025–1045

    work page 2008

  29. [29]

    Another proof for Jackson theorem

    Shen, W., and Zikatanov, L. Another proof for Jackson theorem. http://personal.psu.edu/wxs27/524/JacksonNotes.pdf

    work page

  30. [30]

    Orthogonal Polynomials

    Szeg¨o, G. Orthogonal Polynomials. No. v. 23 in American Mathematical Society colloquium publica- tions. American Mathematical Society, 1975

    work page 1975

  31. [31]

    Tango, W. J. The circle polynomials of zernike and their application in optics. Applied physics 13 , 4 (Aug 1977), 327–332

    work page 1977

  32. [32]

    J., Altman, R

    Yu, K.-H., Zhang, C., Berry, G. J., Altman, R. B., R ´ e, C., Rubin, D. L., and Snyder, M. Predicting non-small cell lung cancer prognosis by fully automated m icroscopic pathology image features. Nature Communications 7 (2016). A Chebyshev Reduction to sparse FFT For completeness, in this section we show how to solve the sparse ap proximation problem for...

    work page 2016

  33. [33]

    Then ˆy[j] = N− 1∑ ℓ=0 y[ℓ]ω jℓ = N− 1∑ ℓ=0 x[ℓ− s]ω j(ℓ− s)ω js = ω js ˆx[j]

    Shifting x scales ˆx elementwise, and vice versa: Consider x∈ CN and y such that y[ℓ] = x[ℓ− s] for all ℓ∈ [N ]. Then ˆy[j] = N− 1∑ ℓ=0 y[ℓ]ω jℓ = N− 1∑ ℓ=0 x[ℓ− s]ω j(ℓ− s)ω js = ω js ˆx[j]. If y[ℓ] = x[ℓ]ω ℓs, then ˆy[j] = N− 1∑ ℓ=0 y[ℓ]ω jℓ = N− 1∑ ℓ=0 x[ℓ]ω (j+s)ℓ = ˆx[j + s]

    work page

  34. [34]

    51 ˆx[j] = ∑ ℓ even x[ℓ]ω jℓ N = N/ 2− 1∑ ℓ=0 x[2ℓ]ω jℓ N/ 2 for j = 0,

    If x is supported only on the first half, then the even indices of ˆx can be computed by a DFT of half the size, and vice versa: ˆx[2j] = N/ 2− 1∑ ℓ=0 x[ℓ]ω 2jℓ N = N/ 2− 1∑ ℓ=0 x[ℓ]ω jℓ N/ 2. 51 ˆx[j] = ∑ ℓ even x[ℓ]ω jℓ N = N/ 2− 1∑ ℓ=0 x[2ℓ]ω jℓ N/ 2 for j = 0, . . . , N/ 2− 1

    work page

  35. [35]

    x is symmetric ( x[i] = x[− i]) if and only if ˆx is symmetric. ˆx[j] = N− 1∑ ℓ=0 x[ℓ]ω jℓ = N− 1∑ ℓ=0 x[− ℓ]ω jℓ = N− 1∑ k=0 x[ℓ]ω− jℓ = ˆx[− j] A.2 Sparse DCT Setup Consider the Chebyshev transform ˆc =Cc ˆc[j] = N− 1∑ ℓ=0 c[ℓ]Tℓ(λ j) (64) where λ j = cos ( π 2j+1 2n ) are the Chebyshev nodes. Note that Tℓ(λ j) = cos ( π 2N ℓ(2j + 1) ) by properties of ...

    work page

  36. [36]

    First observe that most roots of Jacobi polynomials are close en ough to the roots of the Chebyshev polynomials. In particular, by a tighter version of Theorem 5.2 for the special case of − 1/ 2≤ α, β ≤ 1/ 2, we know that the ℓth root is given by cos θℓ, where θℓ = (ℓ+˜ℓ)π N + α +β +1 2 , for some 0 < ˜ℓ < 1 (Theorem 6.3.2 in [31]). So at least for the mo...

    work page

  37. [37]

    error-correction

    Like in Section 5, we just try and do some “error-correction” to obtain cosine eva luations at regular points. Indeed, this is what the trick of cos A = cos(A+B)+cos(A− B) 2 cos B for random B helped us do for the special case of k = 1. However, this approach fails even for k = 2 since we no longer have ‘common terms’ that cancel like they did in proof of...

    work page

  38. [38]

    D More on Jacobi polynomials We begin by collecting more results on Jacobi polynomials and more gen erally orthogonal polynomials in Appendices D.1 and D.2 respectively

    and ( 70) implies that for every i, j ∈ [N ], ⏐ ⏐eT i BT Bej− δi,j ⏐ ⏐≤ 2δ′, which completes the proof (since ( BT B ) [i, j ] = eT i BT Bej). D More on Jacobi polynomials We begin by collecting more results on Jacobi polynomials and more gen erally orthogonal polynomials in Appendices D.1 and D.2 respectively. Finally, we prove Theorem 5.8 in Appendix D....

    work page

  39. [39]

    assigned

    is equation (1.71.7) in [ 31]. Further, ( 74) follows by combining ( 73) and ( 71). In the rest of the proof, we argue ( 72) and ( 73). We begin with ( 73). We will argue that there is a large enough ν0 (that depends on C0) for which there is a constant γ0 (such that|γ0|< 1) with the following property. For every ν≥ ν0, we have that |bν|≤ (γ0)ν , (75) 16T...

    work page