The randomly pivoted Cholesky algorithm is one of the leading methods for computing a low-rank approximation to a large positive-semidefinite matrix. However, while it consistently achieves accuracy comparable to or better than competing methods of its type in experiments, its theoretical analysis lags somewhat behind other methods. This paper closes this gap, proving that randomly pivoted Cholesky produces an approximation with expected error within a $1+\varepsilon$ factor of the optimal rank-$r$ approximation in $\mathcal{O}(r/\varepsilon + r\sqrt{\log r})$ steps. This result nearly matches the optimal complexity $\Theta(r/\varepsilon)$ for any low-rank approximation method based on a partial Cholesky decomposition (also known as a column Nystr\"om approximation). The paper also presents bounds on the randomly pivoted Cholesky trace and spectral-norm errors that hold with high probability. The mathematical argument is largely due to GPT 5.6-Sol (Pro), with some refinements by the author.
In this work, we present the comprehensive rounding error analysis of RCLUPPr proposed in \cite{RCLUPP}, which is a novel randomized CholeskyQR-type algorithm performing LU decomposition with partial pivoting (LUPP decomposition) directly on the tall-skinny $X\in\mathbb{R}^{m\times n}$ with $m \ge n$ and $\mbox{rank}(X)=n$. In contrast to the existing RCLUPP in \cite{RCLUPP}, which applies matrix sketching before LUPP decomposition, RCLUPPr places LUPP decomposition as a preconditioning step first, significantly reducing error propagation. Our analysis rigorously proves that RCLUPPr enjoys markedly better applicability to the ill-conditioned matrices than the existing CholeskyQR-type algorithms and remains stable and accurate in the mixed-precision arithmetic. We further propose practical acceleration strategies in the real implementations of RCLUPPr. Extensive numerical experiments on the real-world problems confirm the theoretical results in this work, demonstrating the robustness and practicality of RCLUPPr in the single, double, and the mixed-precision architecture.
Haoran Guan, Zhenyu Zou, Yufeng Wei et al.· 0 citations
We prove universality of limiting local eigenvalue statistics for random matrices over $\mathbb{Z}_p$. In previous work of the author and Van Peski (arXiv:2601.06283), the limiting eigenvalue correlation functions of additive Haar random matrices were studied in arbitrary finite extensions of $\mathbb{Q}_p$. The same Haar random matrix model plays a central role in the Ellenberg-Jain-Venkatesh heuristic for zeros of $p$-adic $L$-functions. We show that its limiting local eigenvalue statistics are unchanged for a broad class of random matrices with independent entries satisfying a mild non-concentration condition. Thus the random matrix predictions underlying the Ellenberg-Jain-Venkatesh heuristic are not artifacts of the particular Haar ensemble, but instead reflect universal limiting eigenvalue statistics. In this sense, our results provide additional theoretical support for the robustness of their random matrix heuristic. Our proof is based on a new framework, which we call the resultant distribution method. The method recovers limiting laws and root statistics of $p$-adic polynomials from the distributions of their resultant valuations against fixed test polynomials, together with suitable degree estimates. As a second application, we consider random $p$-adic polynomials with independent coefficients satisfying a mild non-concentration condition. Caruso (arXiv:2110.03942) determined the joint root correlation functions of the Haar coefficient model over finite extensions of $\mathbb{Q}_p$. We prove that, for roots of absolute value one, these limiting correlation functions are universal and persist for a broad class of independent coefficient distributions.
We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an $n \times n$ positive-semidefinite (psd) matrix: that is, to sample a column with probability proportional to its squared $\ell_2$-norm. The algorithm runs in just $O(n)$ expected time, which is significantly sublinear in the input matrix size. The runtime is optimal, even when the input is assumed to be diagonal. Our result has several applications. Length-squared sampling is used by a number of sublinear time algorithms for matrix problems, like low-rank approximation and eigenvalue approximation. Often, it is assumed that the algorithm is given access to the matrix column norms, and thus can perform length-squared sampling efficiently. Our result shows that, at least for psd matrices, we can remove this assumption. We also discuss an application to an asymptotically optimal algorithm for estimating the Frobenius norm of a psd matrix to relative error. Finally, we show that our sampling algorithm yields a very simple sublinear time algorithm for the robust psd low-rank approximation problem introduced by Bakshi et al. (FOCS, 2020), which nearly matches the more complex method developed there.
Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco et al.· 0 citations
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm \epsilon)$ error, Bujanovi\'c et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/\epsilon^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/\epsilon^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/\epsilon^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.
The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.
Key ranking is a critical subject for evaluators since it measures the remaining complexity after a side-channel attack without the need to implement the key enumeration algorithm. This paper proposes a novel method based on the knapsack counting problem. While the existing literature proposes a solution of this problem with an algorithm originating from linear programming, we propose a new computation inspired by a recent work in statistical physics. The partition function of the knapsack problem, which is equivalent to the key rank, is derived with an analytic expression. This is used to prove the mathematical equivalence between the knapsack and histogram-based methods. In addition, a saddle-point approximation of the key rank is computed from the analytic expression. A very simple mathematical formula is derived. Simulation results show that the approximation is very tight. In addition, the execution time of the approximation is fast and linear in the key size, making it suitable for scaling to very large keys.
M. Noes· IACR Communications in Crypt...· 0 citations