Research map / Learning theory and algorithms / Matrix and tensor methods
Discrepancy Minimization in Input-Sparsity Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a combinatorial input-sparsity-time algorithm for discrepancy minimization of real-valued matrices matching Larsen's approximation guarantee, plus an FMM variant running in nnz(A)+n^2.53 time.
Problem
Finding a low-discrepancy coloring x in {-1,1}^n of a real-valued m x n matrix A quickly; prior real-valued algorithms (Bansal SDP, Larsen combinatorial) are too slow for input-sparsity time.
Approach
Replaces the explicit projection computations in Larsen's algorithm with JL sketches and implicit leverage-score sampling, and speeds up the iterative Edge-Walk partial-coloring via a lazy guess-and-correct data structure with batched Gaussian projections and low-rank corrections.
Key results
- Combinatorial algorithm runs in Otilde(nnz(A)+n^3) time with disc(A,x)=O(herdisc(A) log n log^1.5 m), matching Larsen's guarantee.
- FMM-based variant runs in Otilde(nnz(A)+n^2.53) time, breaking the cubic barrier for square matrices.
- Fast hereditary projection subroutine runs in Otilde(nnz(A)+n^omega) time, improving Larsen's O(mn^2) or O(mn^(omega-1)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed FMM-based algorithm instead of Larsen's algorithm | Discrepancy minimization for real-valued matrices · Real-valued m × n matrices | runtime: \widetilde{O}(mn^2 + n^3) -> \widetilde{O}(\mathrm{nnz}(A) + n^{2.53}) | Helped |
| Use the proposed combinatorial algorithm instead of Larsen's algorithm | Discrepancy minimization for real-valued matrices · Real-valued m × n matrices | runtime: \widetilde{O}(mn^2 + n^3) -> \widetilde{O}(\mathrm{nnz}(A) + n^3) | Helped |
| Use the proposed algorithm instead of Larsen's algorithm | Discrepancy minimization for real-valued matrices · Real-valued m × n matrices | discrepancy approximation guarantee: O( \herdisc(A) \cdot \log n \cdot \log^{1.5} m ) | No clear effect |
| Use the proposed FMM-based algorithm instead of Bansal's SDP algorithm | Discrepancy minimization for real-valued matrices · Real-valued m × n matrices | runtime: \widetilde{O}(mn^{4.5}) -> \widetilde{O}(\mathrm{nnz}(A) + n^{2.53}) | Helped |
Surprising findings
- Runtime is barely sensitive to improvements in the dual matrix multiplication exponent; even alpha near 1 would only improve the additive term exponent by about 0.03.
- The approach appears limited to about n^2.5 because the tradeoff term cannot go below that without an ideal omega.
Limitations
- Speedup over n^3 depends on fast matrix multiplication; the FMM-free version remains cubic in n.
- Approximation guarantee is logarithmic in herdisc(A) with extra log factors, and the algorithm is randomized with high-probability guarantees only.
Experimental setup
Metrics: running time discrepancy approximation ratio relative to herdisc
Baselines: Bansal SDP algorithm Larsen combinatorial algorithm Eldan-Singh LP-based algorithm
Builds on: Larsen combinatorial discrepancy algorithm Bansal SDP discrepancy algorithm Lovett-Meka Edge-Walk Jain-Sah-Sawhney binary matrix coloring
Closest papers by meaning
- Sublinear Time Numerical Linear Algebra for Structured Matrices (AAAI 2019 · similarity 0.82)
- Faster Algorithms for Binary Matrix Factorization (ICML 2019 · similarity 0.82)
- The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.81)
- Generative Sliced MMD Flows with Riesz Kernels (ICLR 2024 · similarity 0.80)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.80)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.