PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi

arXiv:1111.1491v1cs.DScs.NAmath.CAmath.NA

TL;DR

Balanced separator is a classic NP-hard graph-partitioning problem with applications including recursive algorithms, clustering, and scientific computation. The paper develops a random-walk-based spectral algorithm and matrix-exponential methods; BALSEP either finds a low-conductance balanced cut or certifies that none meets the target.

  • Problem

    Balanced separator asks whether a graph has a b-balanced cut with conductance at most a target γ, for a classic NP-hard problem with applications in recursive algorithms, clustering, and scientific computation.

    Source: §1.1 · p. 3

  • Method

    The algorithm uses a multidimensional embedding from an accelerated heat-kernel random walk, simulated for τ = log n/γ to emphasize cuts of the desired conductance.

    Source: §3.1.2 · p. 7

  • Results

    BALSEP runs in O(m poly(log n)) time and either finds an Ω(b)-balanced cut of conductance O(√γ) or certifies that no b-balanced cut has conductance at most γ.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The paper establishes an asymptotically optimal ˜O(m) spectral algorithm for balanced separator and also provides a simple, practical algorithm.

    Source: §4 · p. 15

    The authors report that the proposed hypothesis for fast matrix-exponential computation remains unproved for general PSD matrices and that they are far from proving it.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt(\gamma)) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in time \tilde{O}(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute \exp(-L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to \exp(-A)v for a class of PSD matrices A and a given vector u, in time roughly \tilde{O}(m_A), where m_A is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting SDD matrices in \tilde{O}(m_A) time. Finally, we prove e^{-x} can be uniformly approximated up to a small additive error, in a non-negative interval [a,b] with a polynomial of degree roughly \sqrt{b-a}. While this result is of independent interest in approximation theory, we show that, via the Lanczos method from numerical analysis, it yields a simple algorithm to compute \exp(-A)v for PSD matrices that runs in time roughly O(t_A \sqrt{||A||}), where t_A is the time required for computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(\sqrt(\gamma)), for balanced separator that runs in time \tilde{O}(m/\sqrt(\gamma)). This latter algorithm matches the running time, but improves on the approximation guarantee of the algorithm by Andersen and Peres.

1 Introduction and Our Results

The paper develops spectral algorithms for balanced separator and fast methods for computing matrix-exponential–vector products. Its results include a nearly-linear-time balanced-separator guarantee and a simpler Lanczos-based alternative, alongside bounds for polynomial approximation of e^-x.

1.1 Balanced Separator

  • BALSEP runs in O(m poly(log n)) time and either finds an Ω(b)-balanced cut of conductance O(√γ) or certifies that no b-balanced cut has conductance at most γ.The theorem assumes constant b = Ω(1).Source: §1.1 · p. 3
  • The simpler practical balanced-separator algorithm improves the approximation guarantee over Andersen and Peres at the same running time.The paper describes it as an alternative to its nearly-linear-time algorithm.Source: §1.1 · p. 3

1.1.1 Comparison to Previous Work on Balanced Separator

  • Earlier approaches include an O(log n)-approximation using SDP and flow ideas, while RLE can require quadratic time in the worst case.RLE repeatedly applies the Laplacian Eigenvector algorithm to remove low-conductance unbalanced cuts.Source: §1.1.1 · p. 4
  • Spielman and Teng gave nearly-linear-time algorithms with O(√γ polylog n) output conductance when a b-balanced cut of conductance below γ exists.Local random walks remove unbalanced cuts in time proportional to the size of each removed cut.Source: §1.1.1 · p. 4

1.2 The Matrix Exponential, the Lanczos Method and Approximations to e−x

  • For an n × n SDD matrix A, the algorithm approximates exp(-A)v within δ||v|| in ˜O((m_A+n) log(2+||A||)) time, hiding poly(log n) and poly(log 1/δ) factors.The balanced-separator application uses the Spielman–Teng solver in a non-trivial way.Source: §1.2 · p. 5
  • For arbitrary symmetric PSD matrices with ||A|| = ω(poly(log n)), the paper gives an algorithm for approximating exp(-A)v.The supplied theorem passages do not preserve its full running-time bound.Source: §1.2 · pp. 5–6
  • The simple PSD method uses matrix-vector products without matrix inversion, avoiding the associated inversion-error analysis and yielding a practical balanced-separator algorithm.Its balanced-separator application has running time ˜O(m/√γ).Source: §1.2 · p. 6
  • The paper proves upper and lower bounds for polynomial approximation of e^-x, with the lower bound showing the degree cannot improve beyond lower-order terms.The approximation result is also presented as independently interesting and relevant to improving the simple algorithm's running time.Source: §1.2 · p. 6

2 Organization of the Main Body of the Paper

The paper first gives an overview of its results and open problems, then presents proofs and technical details in separate sections.

2 Organization of the Main Body of the Paper

  • Section 5 gives the full description and proofs for Theorems 1.1 and 3.1.These are the balanced-separator results.Source: §2 · p. 6
  • Section 6 presents matrix-exponential results, including proofs of Theorems 1.2, 1.4, and 3.2.Source: §2 · p. 6
  • Section 7 proves the structural results on approximating e^-x and Theorem 1.5.Source: §2 · p. 6

3 Technical Overview of Our Results

This overview presents BALSEP’s accelerated heat-kernel approach to balanced cuts and algorithms for approximating matrix exponentials. It covers Lanczos-based approaches, polynomial approximation of e^-x with square-root dependence on interval width, and the associated error analysis and degree bounds.

3.1 Our Spectral Algorithm for Balanced Separator

  • BALSEP runs in ˜O(m/√γ) time and either finds an Ω(b)-balanced cut of conductance O(√γ) or certifies that no b-balanced cut has conductance below γ.The stated guarantee assumes an unweighted graph and constant b ∈ (0, 1/2], with b = Ω(1).Source: §3.1 · p. 7

3.1.1 Comparison with the RLE Algorithm

  • Unlike RLE, which may require Ω(n) iterations when its second eigenvector captures only one low-conductance cut, BALSEP uses a multidimensional walk embedding to capture several cuts.RLE can fail to make progress when a graph has many loosely connected components around an expander-like core.Source: §3.1.1 · p. 7, §3.1.2 · p. 7

3.1.2 High-Level Idea of Our Algorithm

  • At each iteration BALSEP runs an Accelerated Heat Kernel Walk for τ = log n/γ, whose embedding weights low-eigenvalue directions and can expose multiple low-conductance cuts.When an unbalanced cut is found, the algorithm soft-removes it by accelerating convergence from that vertex set, encouraging a different cut to emerge next.Source: §3.1.2 · pp. 7–8

3.1.4 The AHK Random Walk and its Mixing

  • The AHK walk adds nonnegative weighted star-graph Laplacians to the heat-kernel transition rate, accelerating convergence at vertices with larger weights; its symmetric PSD embedding supports geometric SDP rounding.The algorithm tracks deviation from stationarity as a potential, with β updated from previously found cuts.Source: §3.1.4 · pp. 8–9

3.1.5 Our Algorithm and its Analysis

  • When total deviation is small and the accelerated set has volume at most b/100 · 2m, BALSEP certifies no b-balanced cut has conductance below γ; otherwise, rounding the embedding can yield a cut of conductance O(√γ).If the cut is unbalanced, the algorithm accelerates the walk on it and repeats; potential reduction gives O(log n) iterations, with high probability that an unbalanced cut accounts for at least half the deviation.Source: §3.1.5 · p. 9

3.1.6 Exponential Embeddings of Graph and Proof Ideas

  • For the AHK embedding, small total deviation implies a second-eigenvalue lower bound of about γ, while its Laplacian quadratic form is dominated by eigenvalues below 2γ and is at most O(γ) times the embedding potential.The certificate argument extends to later iterations when the added star Laplacians have small weight and support.Source: §3.1.6 · p. 10

3.2 Our Algorithms to Compute an Approximation to exp(−A)v

  • For A = ΠHMHΠ, with M SDD, positive diagonal H, and rank-(n−1) projection Π, the matrix-exponential algorithm approximates exp(−A)v to error δ∥v∥ in ˜O((mM + n) log(2 + ∥HMH∥)) time.The proof extends the SDD solver using the Sherman–Morrison formula because A itself may be neither sparse nor SDD.Source: §3.2 · pp. 10–11

3.2.1 Lanczos Method

  • Lanczos approximates f(B)v by a low-degree polynomial in B, with error bounded by the best uniform polynomial-approximation error over B’s spectrum and runtime roughly O((tB + n)k + k^2).For e^-x, the SSV result supplies degree-k rational-form polynomials with error O(k · 2^-k) on [0, ∞); adapting Lanczos for inexact inverse products requires an orthonormal basis and an upper-Hessenberg matrix.Source: §3.2.1 · p. 11, Our Algorithm · pp. 12–13

3.2.2 Approximating exp(−A)v Using a Rational Approximation to e−x

  • The rational-approximation method uses the Spielman–Teng SDD solver to approximate (I + A/k)^−1v, with an error analysis that accounts for approximate inversions.The analysis relies on an SSV approximation result better than the variant used by EH, whose shifting-technique proof is described as incorrect; the error analysis is highly technical.Source: Our Algorithm · p. 13, Error Analysis · p. 13

3.2.3 Approximation Using Our Polynomial Approximation to e−x

  • Combining Lanczos with the polynomial approximation yields u satisfying ∥exp(−A)v − u∥ ≤ δ ∥v∥∥exp(−A)∥, and avoids inverse computation.The procedure and proofs are simpler, and the algorithm is described as practical.Source: §3.2.3 · pp. 13–14

3.3 Our Uniform Approximation for e−x

  • The polynomial approximation achieves error δ · e^−a on [a, b] with degree of order √(b − a) · poly(log 1/δ), and a matching lower bound holds up to polylogarithmic factors.The upper bound is obtained by composing a polynomial approximation to (1 + x/k)^−1 with a polynomial in that approximation; the lower bound uses Markov’s theorem.Source: Upper Bound · pp. 14–15

4 Discussion and Open Problems

The paper presents an asymptotically optimal O(m) spectral algorithm for balanced separator and a simple, practical alternative. It identifies open questions about stronger certificates, matrix-exponential approximation, and polynomial approximation of e^-x.

Contributions

  • The paper combines techniques from random walks, SDPs, numerical linear algebra, and approximation theory to present an asymptotically optimal O(m) spectral algorithm for balanced separator and a simple, practical algorithm.Source: §4 · p. 15

Open problems

  • The main open question is whether stronger certificates ruling out sparse balanced cuts can be obtained in nearly-linear time.The paper’s certificate supports decompositions into components that are subsets of induced expanders, but is weaker than the certificate that outputs a large-volume induced expander.Source: §4 · p. 15
  • Settling the matrix-exponential approximation hypothesis remains open, and the error analysis needed for the results is long and difficult.The paper calls for a more illuminating proof of that analysis.Source: §4 · p. 15
  • The paper leaves open closing the gap between upper and lower bounds for polynomial approximations to e^-x on [a, b].Source: §4 · p. 15

5 The Algorithm for Balanced Separator

BALSEP replaces RLE’s eigenvector embedding with an Accelerated Heat Kernel walk, then adjusts the walk to mix across unbalanced low-conductance cuts. Its deviation-from-stationarity test and cut-finding routine yield either a balanced cut or a certificate.

5.2 AHK Random Walks

  • AHK processes use transition rate Q(β) = −(L + Σ_i β_iL(S_i))D⁻¹; star terms accelerate mixing from vertices with larger β_i.Probability mass leaving those vertices is distributed uniformly over the graph’s edges.Source: §5.2 · p. 17
  • The columns of D⁻¹ᐟ²Pτ(β) form an embedding whose Gram matrix is positive semidefinite, enabling geometric SDP analysis.Johnson–Lindenstrauss projection reduces the embedding to O(log n) dimensions while approximately preserving distances.Source: Embedding View · p. 17, §5.3 · p. 18

5.3 Algorithm Description

  • BALSEP uses FINDCUT for SDP rounding and EXPV to approximate walk-transition products; EXPV can use either the Spielman–Teng-based method or Lanczos.The algorithm may output FAIL, which the authors state occurs only with small probability.Source: §5.3 · p. 18
  • At each iteration, BALSEP estimates total deviation from stationarity; if it is not small, FINDCUT seeks a low-conductance cut.A sufficiently balanced cut, or its union with previously found cuts, can be output; otherwise β is increased on the unbalanced cut to accelerate mixing across it.Source: §5.3 · p. 19
  • Unlike RLE, BALSEP uses the AHK-walk embedding instead of an eigenvector and updates β rather than removing unbalanced low-conductance cuts.The update makes the next walk mix across the unbalanced cuts found so far.Source: §5.3 · p. 19

5.4 Analysis

The analysis treats total deviation from stationarity as a potential: small deviation certifies the absence of a low-conductance balanced cut, while each unbalanced cut found drives the potential down. This yields logarithmically many iterations and near-linear running time.

5.4 Analysis

  • If the walk’s total deviation is sufficiently small, no b-balanced cut of conductance less than γ exists, because acceleration is confined to a small unbalanced set.A balanced low-conductance cut would not have its mixing greatly helped by acceleration over that set.Source: Potential Guarantee · p. 20
  • When mixing remains insufficient, the embedding has low quadratic form relative to the graph Laplacian, supporting FINDCUT’s recovery of a low-conductance cut.FINDCUT’s stated guarantee is a cut with conductance O(√γ), with balance or additional conditions described in Theorem 5.8.Source: The Deviation of an Unbalanced Cut · p. 20
  • An unbalanced cut found by FINDCUT contributes a large constant fraction of total deviation, and accelerating from that set eliminates at least a constant fraction of the potential.The decrease argument uses stability of the walk and the Golden–Thompson inequality.Source: The Deviation of an Unbalanced Cut · p. 21, Potential Reduction · p. 21
  • With high probability, each nonterminal iteration reduces the potential to at most 5/6 of its previous value, so after at most 12 log n iterations the algorithm certifies no b-balanced cut of conductance less than γ.The proof also identifies a balanced low-conductance cut as an alternative termination outcome.Source: Potential Reduction · p. 21
  • The Spielman–Teng-based implementation computes each matrix-exponential-vector product in Õ(m) time, and the full algorithm runs in Õ(m) time.There are at most O(log n) iterations, each with Õ(m) work.Source: Potential Reduction · p. 22

5.5 Proofs

The proofs connect the random-walk potential to matrix traces, show how small potential certifies conductance, and establish that unbalanced cuts drive a constant-factor decrease. Together these lemmas justify BALSEP’s certificate and iteration progress.

5.5.2 Useful Lemmata

  • The total deviation potential equals Tr(e⁻²τC(t)) − 1, expressing the walk’s mixing behavior through the spectrum of C(t).The identity follows by rewriting the transition matrix in terms of C(t) and using the trace’s cyclic property.Source: §5.5.2 · p. 23

5.5.3 Proof of Lemma 5.6

  • The proof bounds the acceleration weights and compares a balanced cut’s vector to the resulting matrix inequality to conclude its conductance is at least γ.The stated bound uses vol(S) ≤ b·2m/100 and yields φ(U) ≥ γ.Source: §5.5.3 · p. 24

5.5.4 Proof of Lemma 5.7

  • The eigenvalue argument splits the spectrum of C(t) into ranges around 24γ before combining bounds and applying Johnson–Lindenstrauss.This establishes the embedding estimates used to relate the walk’s potential to cut-finding.Source: §5.5.4 · pp. 24–25

5.5.5 Proof of Corollary 5.9

  • The cut-finding guarantee and the embedding bounds imply that a found cut is either c-balanced or accounts for at least 2/3 of the total deviation.The corollary then gives, with high probability, at least half of total deviation on the found unbalanced cut.Source: §5.5.5 · p. 25

5.5.6 Proof of Theorem 5.10

  • The potential decrease follows by applying Golden–Thompson, bounding the added star-Laplacian terms, and using the deviation concentrated on the unbalanced cut.The proof’s final step invokes the corollary’s high-probability bound on deviation over S(t).Source: §5.5.6 · p. 25

5.6 SDP Interpretation

The SDP interpretation explains BALSEP’s iteration reduction as a change to the starting candidate solution. This makes the update width O(γ), reducing the required number of iterations to O(log n).

5.6 SDP Interpretation

  • OV’s algorithm uses MMWU updates and FINDCUT to obtain a dual certificate, with O(log n/γ) iterations needed to certify SDP infeasibility.The update width is Θ(1), dominated by the first of the two update types.Source: §5.6 · p. 26
  • BALSEP changes the initial candidate from Y(1) ∝ D⁻¹ to a heat-kernel-based X(1), which ensures L • X(t) ≤ O(γ)·L(KV) • X(t) or yields an infeasibility certificate.This permits bypassing the prior update type and using updates of width O(γ), requiring O(log n) iterations.Source: §5.6 · p. 26
  • The authors interpret the change as regrouping the possible τ ≅ log n/γ updates of OV’s Equation 2 into one initial step.Source: §5.6 · p. 26

5.7 The FINDCUT Subroutine

FINDCUT uses an embedding to seek a balanced cut, relying on sweep-cut and projection-rounding arguments. Its guarantee also bounds retained embedding variance when the balanced-cut outcome does not hold.

5.7.1 Preliminaries

  • The tailored sweep-cut lemma finds a cut of low conductance when a nonnegative vector has bounded energy, bounded support volume, and sufficient mass.The argument is designed to retain a constant fraction of the embedding’s variance inside the output cut.Source: §5.7.1 · p. 27

5.7.2 Roundable Embeddings and Projections

  • A roundable embedding yields an Ω(b)-balanced cut with conductance O(√α) through PROJROUND.The rounding procedure runs with high probability in time ˜O(nh + m).Source: §5.7.2 · p. 27

5.7.3 Description of FINDCUT

  • FINDCUT either returns a c-balanced set C or guarantees that the embedding’s variance on R is at least two-thirds of its total variance.The theorem assumes L • X(t) ≤ αL(KV) • X(t), with c = Ω(b) and c ≤ b/100.Source: §5.7.3 · p. 28
  • FINDCUT runs in time ˜O(md) for an embedding in d dimensions.The stated runtime accounts for the embedding operations, sweep, and projection rounding.Source: §5.7.3 · p. 30

6 Computing exp(−A)v

This section presents two procedures for approximating exp(−A)v for symmetric PSD matrices: EXPRATIONAL uses an inverse routine, while LANCZOS uses polynomial approximation. Their guarantees connect exponential approximation to the cost of matrix-vector operations or inversion.

Algorithms for Theorem 1.2, 1.3 and 3.2

  • EXPRATIONAL approximates exp(−A)v to error δ using an InvertA oracle for a symmetric PSD matrix.Its runtime depends on the cost of the required InvertA calls and the algorithm parameters.Source: §6 · p. 30
  • The two procedures differ in how they implement InvertA: the paper uses a Spielman–Teng SDD solver, and combines it with Sherman–Morrison for rank-one updates.These implementations support Theorems 1.2 and 3.2, respectively.Source: §6 · pp. 30–31

Algorithm for Theorem 1.4

  • LANCZOS approximates exp(−A)v with error at most ∥exp(−A)∥δ, using time O((n + tA)k + k²).The parameter k depends on the eigenvalue range and δ.Source: §6 · p. 31

6.1 Lanczos Method – From Scalars to Matrices

Lanczos approximates f(B)v by restricting B to the Krylov subspace generated from v, so its accuracy is tied to polynomial approximation of f over the spectrum. For symmetric B, the basis construction produces a tridiagonal restricted matrix and can be computed efficiently.

6.1 Lanczos Method – From Scalars to Matrices

  • The Krylov subspace consists of the span of v, Bv, …, B^kv, and degree-k polynomial actions on B applied to v lie in this subspace.Lanczos computes the approximation in this reduced space rather than diagonalizing B directly.Source: §6.1 · p. 31
  • The Lanczos approximation is at least as accurate as the best degree-k polynomial approximation to f over the spectrum of B.The polynomial component is computed exactly in the approximation; the remaining error is bounded by the uniform approximation error.Source: §6.1 · p. 32

6.1.1 Efficiently Computing a Basis for the Krylov Subspace

  • For symmetric B, Lanczos builds a tridiagonal restricted matrix Tk, requiring orthogonalization only against the two preceding basis vectors.This structure lets the procedure compute f(Tk) in O(k²) time, for total time O((n + tB)k + k²).Source: §6.1.1 · pp. 33–34

6.2 Procedures for Approximating exp(−A)v.

The section develops two Lanczos-based approaches to approximate exp(−A)v: direct polynomial approximation on the spectrum, and a rational approximation implemented through approximate inverse solves. The latter introduces solver error that requires separate analysis.

6.2.1 Using LANCZOS for Approximating exp(−A)v – Proof of Theorem 1.4

  • Direct LANCZOS approximation of exp(−A)v uses a polynomial whose degree depends on the spectral interval and target error, with runtime O((n + tA)k + k²).The polynomial approximation bound is applied over [λn(A), λ1(A)].Source: §6.2.1 · p. 34

6.2.2 The EXPRATIONAL Algorithm

  • Uniform rational approximations to exp(−x) on [0, ∞) have error that decays exponentially with degree.The cited result is described as asymptotically best possible.Source: §6.2.2 · p. 34
  • EXPRATIONAL applies Lanczos to a transformed matrix B = (I + A/k)⁻¹ and a function of B to approximate exp(−A)v.This corresponds to approximating exp(−y) by degree-k polynomials in (1 + y/k)⁻¹.Source: §6.2.2 · p. 35
  • Approximate inverse solves replace exact Lanczos computations, so their errors can propagate rapidly through the iterations and require dedicated analysis.The paper identifies this error analysis as a significant technical component.Source: §6.2.2 · p. 35

6.3 Exponentiating PSD Matrices – Proofs of Theorem 1.2 and 3.2

This section proves matrix-exponential approximation guarantees by combining EXPRATIONAL with suitable inverse procedures. For SDD matrices, the resulting approximation runs in nearly linear time; general PSD matrices use Conjugate Gradient.

6.3 Exponentiating PSD Matrices – Proofs of Theorem 1.2 and 3.2

  • In this section, the proofs of Theorems 1.2 and 1.3, assuming Theorem 6.1, use algorithms that combine EXPRATIONAL with appropriate InvertA procedures.Source: §6.3 · p. 35

6.3.1 SDD Matrices – Proof of Theorems 1.2

  • For SDD A, an approximation u to exp(−A)v with error at most δ∥v∥ is computed in time ˜O((mA + n) log(2 + ∥A∥)), hiding poly(log n) and poly(log 1/δ) factors.The proof implements InvertA by approximately solving (I + A/k)z = y with the Spielman–Teng SDD solver.Source: §6.3.1 · p. 37

6.3.2 General PSD Matrices – Proof of Theorem 1.3

6.4 Beyond SDD - Proof of Theorem 3.2

For A = ΠHMHΠ, with SDD M and positive diagonal H, the section constructs an inverse procedure for EXPRATIONAL. It uses the known projection direction and an SDD solver to retain a nearly linear-time exponential approximation.

6.4 Beyond SDD - Proof of Theorem 3.2

  • For A = ΠHMHΠ, the algorithm approximates exp(−A)v within δ∥v∥ in time ˜O((mM + n) log(2 + ∥HMH∥)), hiding poly(log n) and poly(log 1/δ) factors.The guarantee assumes M is SDD, H has strictly positive diagonal entries, and Π projects onto a rank n−1 subspace with known unit vector w.Source: §6.4 · p. 38
  • Applying the SDD solver to M and multiplying by H−1 yields the required approximate inverse of HMH in time ˜O((mM + n) log n log 1/ε1).Because H is diagonal, multiplication by H−1 takes O(n) time.Source: §6.4 · p. 39
  • The inverse procedure splits the input into components along w and orthogonal to w, then uses a rank-one correction to invert the orthogonal component.The correction is expressed using the Sherman–Morrison formula, while the base inverse is computed through an SDD solver.Source: §6.4 · p. 40

6.5 Error Analysis for EXPRATIONAL

The error analysis controls how approximate inverse computations affect EXPRATIONAL’s coefficient matrix and output. It bounds errors in polynomial computations and then uses polynomial approximation to control the exponential remainder.

6.5 Error Analysis for EXPRATIONAL

  • Approximate inverse calls introduce errors across the iterations, so the analysis bounds the coefficient matrix spectrum and the accumulated error in powers of the matrix.The proof expresses the final error as a sum of iteration-specific contributions and bounds their propagation.Source: Proof Overview · p. 42
  • For degree-at-most-k polynomials, the computation error is bounded by ε2∥p∥1 when approximate powers differ by at most ε2.The exponential analysis separates a polynomial approximation from a remainder and bounds both contributions.Source: Proof Overview · p. 42

6.5.1 Remaining Proofs

  • The remaining proofs establish the coefficient-matrix and power-error bounds used to justify the EXPRATIONAL approximation.Under the stated ε1 and ε2 conditions, the power error is bounded by ε2.Source: §6.5.1 · pp. 45, 47
  • When p(0)=0 and p approximates the exponential on (0,1], its coefficient ℓ1 norm is at most (2k)^(k+1).The proof obtains this bound by interpolation at 0, 1/k, …, 1.Source: §6.5.1 · pp. 48–49

7 Uniform Approximations to e−x

The section studies uniform polynomial approximation of e−x on nonnegative intervals. It establishes upper and lower degree bounds, discusses how interval length changes the approximation regime, and proves the bounds using polynomial constructions and derivative constraints.

7 Uniform Approximations to e−x

  • For e−x on [a,b], the paper proves a uniform-approximation upper bound and a lower bound showing that the interval-width dependence is necessary under the stated conditions.The lower bound applies when b ≥ a + loge 4 and δ ∈ (0,1/8], for error δe−a.Source: §7 · p. 50

7.1 Preliminaries

  • The approximation question is to find the smallest degree polynomial achieving error δe−a uniformly over [a,b].A δ-approximation means the supremum error over the interval is at most δ.Source: §7.1 · p. 50, §7.2 · p. 51

7.2 Known Approximation Results and Discussion.

  • For fixed interval length, the required degree is poly(log 1/δ) and is at least Ω(log 1/δ); for unbounded length, the paper highlights improved dependence on b−a.The comparison distinguishes the paper’s error tolerance δe−a from the smaller Taylor-series error discussed in the section.Source: A lower bound · pp. 51–52

7.3 Proof of Upper Bound in Theorem 1.5

  • The upper-bound proof constructs exponential approximations from polynomial approximations to reciprocal functions, using a shifted and scaled interval and Chebyshev polynomials.The construction proceeds from approximating x−1 to approximating (1 + x/k)−1, then builds the exponential approximation.Source: §7.3 · p. 52

7.4 Proof of Lower Bound in Theorem 1.5

  • The lower-bound proof combines Markov’s derivative bound with the mean value theorem and the assumed uniform-approximation error.This yields the degree lower bound under the theorem’s interval and error conditions.Source: §7.4 · pp. 54–55

7.5 Remaining Proofs

  • The remaining proofs include a uniform-approximation analysis of Taylor polynomials centered at the midpoint of [a,b].The section also supplies proofs for the shifted-interval and reciprocal-approximation lemmas.Source: §7.5 · pp. 55–56
Loading 1111.1491v1…