An O(n)-randomness perturbation combining a dense deterministic pattern matrix with a non-uniform sparse dependent perturbation reduces condition numbers to O(n) for any input matrix.
Derezi´ nski, E
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
years
2026 4representative citing papers
Richardson and a new Krylov method MINBERR achieve universal (condition-free) backward-error rates 1/k and O(1/k^{2}) for PSD linear systems, with a near-universal O(log n / k) extension to general systems.
Establishes non-identifiability results and query lower bounds showing transpose-free matvec access provides limited information for core linear algebra tasks.
Algorithm approximates spectral density of normal matrices to EMD O(1/m + log m/sqrt(n)) with m matvec queries and proves Omega(1/epsilon) lower bound even for symmetric case.
citing papers explorer
-
Well-Conditioned Oblivious Perturbations in Linear Space
An O(n)-randomness perturbation combining a dense deterministic pattern matrix with a non-uniform sparse dependent perturbation reduces condition numbers to O(n) for any input matrix.
-
Towards Universal Convergence of Backward Error in Linear System Solvers
Richardson and a new Krylov method MINBERR achieve universal (condition-free) backward-error rates 1/k and O(1/k^{2}) for PSD linear systems, with a near-universal O(log n / k) extension to general systems.
-
Transpose-free linear algebra
Establishes non-identifiability results and query lower bounds showing transpose-free matvec access provides limited information for core linear algebra tasks.
-
Spectral density estimation for normal matrices
Algorithm approximates spectral density of normal matrices to EMD O(1/m + log m/sqrt(n)) with m matvec queries and proves Omega(1/epsilon) lower bound even for symmetric case.