{"ID":2894565,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.11724","arxiv_id":"2507.11724","title":"Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure","abstract":"We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for $k$ large singular values. For solving such $d \\times d$ positive definite system our algorithms succeed whp. and run in time $\\tilde O(d^2 + k^ω)$. For solving such regression problems in a matrix $\\mathbf{A} \\in \\mathbb{R}^{n \\times d}$ our methods succeed whp. and run in time $\\tilde O(\\mathrm{nnz}(\\mathbf{A}) + d^2 + k^ω)$ where $ω$ is the matrix multiplication exponent and $\\mathrm{nnz}(\\mathbf{A})$ is the number of non-zeros in $\\mathbf{A}$. Our methods nearly-match a natural complexity limit under dense inputs for these problems and improve upon a trade-off in prior approaches that obtain running times of either $\\tilde O(d^{2.065}+k^ω)$ or $\\tilde O(d^2 + dk^{ω-1})$ for $d\\times d$ systems. Moreover, we show how to obtain these running times even under the weaker assumption that all but $k$ of the singular values have a suitably bounded generalized mean. Consequently, we give the first nearly-linear time algorithm for computing a multiplicative approximation to the nuclear norm of an arbitrary dense matrix. Our algorithms are built on three general recursive preconditioning frameworks, where matrix sketching and low-rank update formulas are carefully tailored to the problems' structure.","short_abstract":"We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for $k$ large singular values. For solving such $d \\times d$ positive definite system our algorithms succeed whp. and run in time $\\tilde O(d^2 + k^ω)$. For solving such regression prob...","url_abs":"https://arxiv.org/abs/2507.11724","url_pdf":"https://arxiv.org/pdf/2507.11724v1","authors":"[\"Michał Dereziński\",\"Aaron Sidford\"]","published":"2025-07-15T20:48:30Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.NA\",\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}