Nearly Optimal Approximation of Matrix Functions by the Lanczos Method
Authors: Noah Amsel, Tyler Chen, Anne Greenbaum, Cameron Musco, Christopher Musco
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In Section 4, we present experimental evidence showing that, for many natural problem instances, our bounds are significantly sharper than the standard bound of Fact 3. These experiments also demonstrate that despite its generality, Lanczos-FA often converges significantly faster than other methods in practice. |
| Researcher Affiliation | Academia | New York University (noah.amsel@nyu.edu, tyler.chen@nyu.edu, cmusco@nyu.edu) University of Washington (greenbau@uw.edu) University of Massachusetts Amherst (cmusco@cs.umass.edu) |
| Pseudocode | No | The paper includes mathematical equations, definitions, lemmas, theorems, and proofs, but no structured pseudocode or algorithm blocks are present. |
| Open Source Code | Yes | Code for our experiments is available at https://github.com/Noah Amsel/lanczos-optimality/ tree/neurips2024_near_optimality. |
| Open Datasets | No | The paper describes generating synthetic "test matrices A R100 100" with specific properties for its experiments. It does not use or provide access information for a standard publicly available dataset. |
| Dataset Splits | No | The paper does not mention training, validation, or test data splits in the context of typical machine learning dataset partitioning. |
| Hardware Specification | No | The paper vaguely states, "All experiments were performed on a standard laptop in a few minutes." This does not provide specific hardware details like CPU/GPU models or memory. |
| Software Dependencies | No | The paper mentions using "the flamp library, which is based on mpmath [51]". While mpmath is referenced with version 0.18 in the bibliography, flamp's version is not specified, and no other software dependencies with version numbers are listed explicitly in the text. |
| Experiment Setup | Yes | We use three test matrices A R100 100 which all have condition number 100. The first has a uniformly-spaced spectrum, the second has a geometrically-spaced spectrum, and the third has eigenvalues that are all uniformly-spaced in a narrow interval except for ten very small eigenvalues. We compute the bound from Fact 3 using the Remez algorithm and compute the instance-optimal approximation using least squares regression onto the Krylov basis Q. We choose rational functions to match the functions used for Figure 1. We construct a degree 5 rational approximation to exp( π₯/10) following [63]. We construct a degree 10 approximation to log(π₯) using the BRASIL algorithm [40] and verify that it has real poles outside the interval of the eigenvalues. In particular, for parameters (π , π), consider approximating A πb where A has spectrum π1 = 1 and π2, . . . , π100 evenly spaced between 0.999995 π and π . |