We present a novel leverage score-based sampling strategy for the randomized alternating least squares optimization (ALS) of the canonical polyadic decomposition (CPD-ALS). Unlike previous strategies, we determine row-wise samples for the CPD-ALS problem from the leverage scores of the target tensor which is being decomposed. We demonstrate that, when rows are sampled according to the leverage score distribution of the matricized target tensor, each least squares subproblem of the CPD-ALS problem achieves $(1+\epsilon)-$relative accuracy in the residual norm with probability at least $1-\delta$ using a sampling $s=\frac{R\gamma}{\beta} \max\left(\frac{4}{\delta \epsilon}, \frac{144\ln(2R/\delta)}{\epsilon_{0}^{2}}\right)$, where $\epsilon_{0}$ is a constant, $\beta$ is leverage score's approximation constant, $R$ is the target rank and $\gamma$ captures the coherence between the Khatri Rao product (KRP) of the CPD factor matrices and the exact KRP; $\gamma$ decreases as the ALS iterates converge. To efficiently approximate the leverage score distribution for each matricization of the target tensor without explicitly computing leverage scores we use a randomized strong rank-revealing QR (sRRQR) factorizations, SE-QRCS. By construction, this QR-based leverage score sampling method outperforms previously published schemes as it does not, in principle, require the resampling of the target tensor or recomputing the leverage scores of the KRP, minimizing the computational and storage overhead of the CPD-ALS procedure.
Israa Fakih, Laura Grigori, Karl Pierce· arXiv.org· 1 citation
Iterative diagonalization is the dominant cost of plane-wave density-functional theory (DFT), with search-space orthogonalization scaling particularly quickly with problem size and the number of target states. We present a randomized block Davidson-type eigensolver that replaces Euclidean orthogonalization with randomized Gram-Schmidt in a sketched inner product, requiring only a single pass over the basis while keeping its conditioning bounded independently of the input vectors. This modification changes only the Rayleigh-Ritz step, which becomes a definite generalized Hermitian eigenproblem. Ritz extraction remains exact, preserving true Ritz pairs and the interlacing property that makes each band energy an upper bound on the true one. The method is implemented in mixed precision for CPUs and GPUs from a single Julia code, interfaces matrix-free with DFTK, and is released in the open-source RandESC library. On sparse test problems with a fixed number of eigenpairs, the sketched solver overtakes its deterministic counterpart beyond matrix dimensions of about $2\times 10^4$ and is $25\%$ faster at $5\times 10^5$. In full self-consistent field DFT calculations, however, both Davidson variants outperform the locally optimal block preconditioned conjugate gradient (LOBPCG) reference only by $5$ to $11\%$ in total time, while the additional benefit of sketching is limited. As the number of requested states grows with system size, orthogonalization savings are offset by the generalized eigenproblem. Therefore, the regime in which sketching pays off is set by how the number of wanted states scales with the problem dimension, not by the eigensolver as such.
Moritz Gubler, Taejun Park, Augustin Bussy et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
