Buchumschlag

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dereziński, Michał, Sidford, Aaron
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Numerical Analysis Optimization and Control Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Solving Dense Linear Systems Faster Than via Preconditioning
von: Dereziński, Michał, et al.
Veröffentlicht: (2023)

Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
von: Dereziński, Michał, et al.
Veröffentlicht: (2024)

Towards Universal Convergence of Backward Error in Linear System Solvers
von: Dereziński, Michał, et al.
Veröffentlicht: (2026)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
von: Dereziński, Michał, et al.
Veröffentlicht: (2024)

Randomized Kaczmarz Methods with Beyond-Krylov Convergence
von: Dereziński, Michał, et al.
Veröffentlicht: (2025)

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
von: Chenakkod, Shabarish, et al.
Veröffentlicht: (2026)

The matrix-vector complexity of $Ax=b$
von: Dereziński, Michał, et al.
Veröffentlicht: (2026)

Optimal Embedding Dimension for Sparse Subspace Embeddings
von: Chenakkod, Shabarish, et al.
Veröffentlicht: (2023)

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
von: Chenakkod, Shabarish, et al.
Veröffentlicht: (2024)

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
von: Chenakkod, Shabarish, et al.
Veröffentlicht: (2025)

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
von: Jambulapati, Arun, et al.
Veröffentlicht: (2024)

Well-Conditioned Oblivious Perturbations in Linear Space
von: Chenakkod, Shabarish, et al.
Veröffentlicht: (2026)

Iterative Refinement for $\ell_p$-norm Regression
von: Adil, Deeksha, et al.
Veröffentlicht: (2019)

Distributed Least Squares in Small Space via Sketching and Bias Reduction
von: Garg, Sachin, et al.
Veröffentlicht: (2024)

Truncated Variance Reduced Value Iteration
von: Jin, Yujia, et al.
Veröffentlicht: (2024)

Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm
von: Cai, Xufeng, et al.
Veröffentlicht: (2025)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
von: Gu, Yuzhou, et al.
Veröffentlicht: (2023)

Efficient Convex Optimization Requires Superlinear Memory
von: Marsden, Annie, et al.
Veröffentlicht: (2022)

Solving Matrix Games with Near-Optimal Matvec Complexity
von: Karmarkar, Ishani, et al.
Veröffentlicht: (2026)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
von: Chen, Li, et al.
Veröffentlicht: (2025)

Sparse Submodular Function Minimization
von: Graur, Andrei, et al.
Veröffentlicht: (2023)

On computing approximate Lewis weights
von: Apers, Simon, et al.
Veröffentlicht: (2024)

Stability of the Lanczos Method for Matrix Function Approximation
von: Musco, Cameron, et al.
Veröffentlicht: (2017)

Entropy Regularization and Faster Decremental Matching in General Graphs
von: Chen, Jiale, et al.
Veröffentlicht: (2023)

On Smale's 17th problem over the reals
von: Montanari, Andrea, et al.
Veröffentlicht: (2024)

Balancing Gradient and Hessian Queries in Non-Convex Optimization
von: Adil, Deeksha, et al.
Veröffentlicht: (2025)

Reusing Samples in Variance Reduction
von: Jin, Yujia, et al.
Veröffentlicht: (2025)

Convex optimization with $p$-norm oracles
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Quantum speedups for stochastic optimization
von: Sidford, Aaron, et al.
Veröffentlicht: (2023)

Isotropic Noise in Stochastic and Quantum Convex Optimization
von: Marsden, Annie, et al.
Veröffentlicht: (2025)

Extracting Dual Solutions via Primal Optimizers
von: Carmon, Yair, et al.
Veröffentlicht: (2024)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
von: Garg, Sachin, et al.
Veröffentlicht: (2025)

Exploiting Low-Rank Structure in Max-K-Cut Problems
von: Stevens, Ria, et al.
Veröffentlicht: (2026)

Solving Zero-Sum Games with Fewer Matrix-Vector Products
von: Karmarkar, Ishani, et al.
Veröffentlicht: (2025)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
von: Fountoulakis, Kimon, et al.
Veröffentlicht: (2026)

Online Linear Programming with Replenishment
von: Chen, Yuze, et al.
Veröffentlicht: (2026)

Infrequent Resolving Algorithm for Online Linear Programming
von: Li, Guokai, et al.
Veröffentlicht: (2024)

Optimal Scalarizations for Sublinear Hypervolume Regret
von: Zhang, Qiuyi
Veröffentlicht: (2023)

Optimal Decentralized Smoothed Online Convex Optimization
von: Bhuyan, Neelkamal, et al.
Veröffentlicht: (2024)

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
von: Dereziński, Michał, et al.
Veröffentlicht: (2026)