Sublinear Time Numerical Linear Algebra for Structured Matrices
Authors: Xiaofei Shi, David P. Woodruff4918-4925
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show how to solve a number of problems in numerical linear algebra, such as least squares regression, ℓp-regression for any p 1, low rank approximation, and kernel regression, in time T(A)poly(log(nd))... Our algorithms show that, perhaps surprisingly, most of these optimization problems do not require much more time than that of a polylogarithmic number of matrix-vector multiplications. |
| Researcher Affiliation | Academia | Xiaofei Shi,1 David P. Woodruff1 1Carnegie Mellon University xiaofei.shi@andrew.cmu.edu, dwoodruf@andrew.cmu.edu |
| Pseudocode | Yes | Algorithm 1 Repeated Halving Algorithm 2 Repeated Halving Algorithm 3 Approx Lewis Form |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not report experiments on specific datasets. Therefore, it does not mention dataset availability for training. |
| Dataset Splits | No | The paper is theoretical and does not report experiments requiring validation sets or specific data splits. |
| Hardware Specification | No | The paper does not provide any specific hardware details used for running experiments, as it focuses on theoretical algorithm design and complexity analysis. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers, as it focuses on theoretical algorithm design and complexity analysis. |
| Experiment Setup | No | The paper does not provide details about experimental setup, such as hyperparameters or training settings, as it focuses on theoretical algorithm design and complexity analysis rather than empirical experimentation. |