Papers › Reduced-Rank Regression with Operator Norm Error
Reduced-Rank Regression with Operator Norm Error
Praneeth Kacham, David P. Woodruff
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
A common data analysis task is the reduced-rank regression problem: min_(rank-k X) AX-B, where A ∈ℝ^(n ×c) and B ∈ℝ^(n ×d) are given large matrices and · is some norm. Here the unknown matrix X ∈ℝ^(c ×d) is constrained to be of rank k as it results in a significant parameter reduction of the solution when c and d are large. In the case of Frobenius norm error, there is a standard closed form solution to this problem and a fast algorithm to find a (1+ε)-approximate solution. However, for the important case of operator norm error, no closed form solution is known and the fastest known algorithms take singular value decomposition time. We give the first randomized algorithms for this problem running in time (nnz(A) + nnz(B) + c²) ·k/ε^(1.5) + (n+d)k²/ϵ+ c^ω, up to a polylogarithmic factor involving condition numbers, matrix dimensions, and dependence on 1/ε. Here nnz(M) denotes the number of non-zero entries of a matrix M, and ω is the exponent of matrix multiplication. As both (1) spectral low rank approximation (A = B) and (2) linear system solving (n = c and d = 1) are special cases, our time cannot be improved by more than a 1/ε factor (up to polylogarithmic factors) without a major breakthrough in linear algebra. Interestingly, known techniques for low rank approximation, such as alternating minimization or sketch-and-solve, provably fail for this problem. Instead, our algorithm uses an existential characterization of a solution, together with Krylov methods, low degree polynomial approximation, and sketching-based preconditioning.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections