Cover Image

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jin, Yujia, Karmarkar, Ishani, Musco, Christopher, Sidford, Aaron, Singh, Apoorv Vikram
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Truncated Variance Reduced Value Iteration
by: Jin, Yujia, et al.
Published: (2024)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

Reusing Samples in Variance Reduction
by: Jin, Yujia, et al.
Published: (2025)

Stability of the Lanczos Method for Matrix Function Approximation
by: Musco, Cameron, et al.
Published: (2017)

Solving Matrix Games with Near-Optimal Matvec Complexity
by: Karmarkar, Ishani, et al.
Published: (2026)

Solving Zero-Sum Games with Fewer Matrix-Vector Products
by: Karmarkar, Ishani, et al.
Published: (2025)

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

Eulerian Graph Sparsification by Effective Resistance Decomposition
by: Jambulapati, Arun, et al.
Published: (2024)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, et al.
Published: (2025)

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
by: Jambulapati, Arun, et al.
Published: (2024)

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
by: Dereziński, Michał, et al.
Published: (2025)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Matrix Product Sketching via Coordinated Sampling
by: Daliri, Majid, et al.
Published: (2025)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
by: Diwan, Haya, et al.
Published: (2024)

Coupling without Communication and Drafter-Invariant Speculative Decoding
by: Daliri, Majid, et al.
Published: (2024)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

Query Efficient Structured Matrix Learning
by: Amsel, Noah, et al.
Published: (2025)

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
by: Al-Jazzazi, Yousef, et al.
Published: (2025)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Importance Sparsification for Sinkhorn Algorithm
by: Li, Mengyu, et al.
Published: (2023)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition
by: Aghdaei, Ali, et al.
Published: (2024)

Faster Algorithms for Agnostically Learning Disjunctions and their Implications
by: Diakonikolas, Ilias, et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Faster and Space Efficient Indexing for Locality Sensitive Hashing
by: Verma, Bhisham Dev, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Fully Dynamic Spectral Sparsification of Hypergraphs
by: Goranci, Gramoz, et al.
Published: (2025)

A Faster Generalized Two-Stage Approximate Top-K
by: Samaga, Yashas, et al.
Published: (2025)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
by: Makarychev, Konstantin, et al.
Published: (2025)