Randomized algorithm improves matrix discrepancy with faster matrix multiplication
The Komlós Problem in Matrix-Multiplication Time
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper tackles a mathematical problem about assigning signs to columns of a matrix to keep the total variation in rows low. The authors design a new randomized method that is faster than previous approaches, working close to the best known speeds for multiplying matrices. They improve an existing technique by smoothing the measurement used and reusing calculations to reduce computation time. Their approach also ensures precise results despite working with limited numerical accuracy.
What this means in practice
- •For algorithm developers: Design faster algorithms that control matrix discrepancies, enabling more efficient computations in combinatorial optimization.
- •For machine learning engineers: Improve preprocessing steps in linear algebra tasks where balanced sign assignments to data matrices reduce error or bias.
Authors
Emile Anand, Peter Chen
Abstract
We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.