Transpose-free linear algebra
For researchers in operator learning, inverse problems, and PDE solvers, this work establishes fundamental limitations of transpose-free algorithms, showing they are strictly less powerful than those with transpose access.
This paper proves that matrix-free algorithms using only forward matrix-vector products (no transpose access) face severe theoretical barriers: Krylov methods provide no reliable spectral norm information, and problems like least squares, norm estimation, and column subset selection are non-identifiable. Quantitative lower bounds show that rank-k approximation requires at least n queries and Frobenius norm estimation needs Ω(ε⁻²) queries, matching Hutchinson-type estimators.
We study the limitations of matrix-free algorithms that access a matrix $A$ only through forward matrix-vector products (matvecs) $x \mapsto Ax$, without access to the transpose $A^\top$ or its action. This setting arises naturally in operator learning, inverse problems, and matrix-free PDE solvers, where adjoint evaluations may be unavailable or prohibitively expensive. We show that the lack of transpose access creates severe and sometimes insurmountable theoretical barriers. For Krylov methods, we prove that the sequence of projected operator norms produced by Arnoldi iteration can follow any prescribed nondecreasing curve, showing that forward matvecs alone provide essentially no reliable information about the spectral norm. For several core problems, including least squares, norm estimation, column subset selection, and local maximum volume, we establish non-identifiability results; distinct matrices can generate identical forward-query transcripts while having fundamentally different solutions. We also prove quantitative lower bounds on the number of forward matvecs required for approximation tasks. In particular, any algorithm that computes a near-optimal rank-$k$ approximation must use at least $n$ queries, and estimating the Frobenius norm to relative accuracy $\eps$ requires $Ω(\eps^{-2})$ queries when $n$ is sufficiently large, matching the complexity of Hutchinson-type estimators up to constants. Although some problems remain solvable without transpose access, the transpose-free setting is fundamentally more limited in both identifiability and efficiency.