标题： Khatri-Rao随机投影的改进分析及其应用 显示英文标题

标题： Improved Analysis of Khatri-Rao Random Projections and Applications

摘要： 随机化已成为大规模矩阵和张量分解的强大工具集。 随机算法涉及使用随机矩阵进行草图计算。 一种普遍的方法是将随机矩阵作为标准高斯随机矩阵，其理论已得到充分发展。 然而，这种方法的缺点是生成和乘以随机矩阵的成本可能非常高昂。 Khatri-Rao随机投影（KRPs），通过使用随机矩阵的Khatri-Rao积进行草图获得，提供了一种可行的替代方法，并且生成起来要便宜得多。 然而，与实际观察到的精度相比，使用KRPs的理论保证要悲观得多。 我们尝试通过改进KRPs在矩阵和张量低秩分解中的分析来缩小这一差距。 我们提出并分析了一种新的算法，用于使用KRPs对块结构矩阵（例如，块Hankel）进行低秩近似。 我们还开发了新的算法，以KRPs加速Tucker格式中的张量计算，并给出了所得低秩近似的理论保证。 在合成和真实世界张量上的数值实验展示了所提方法的计算优势。 显示英文摘要

摘要： Randomization has emerged as a powerful set of tools for large-scale matrix and tensor decompositions. Randomized algorithms involve computing sketches with random matrices. A prevalent approach is to take the random matrix as a standard Gaussian random matrix, for which the theory is well developed. However, this approach has the drawback that the cost of generating and multiplying by the random matrix can be prohibitively expensive. Khatri-Rao random projections (KRPs), obtained by sketching with Khatri-Rao products of random matrices, offer a viable alternative and are much cheaper to generate. However, the theoretical guarantees of using KRPs are much more pessimistic compared to their accuracy observed in practice. We attempt to close this gap by obtaining improved analysis of the use of KRPs in matrix and tensor low-rank decompositions. We propose and analyze a new algorithm for low-rank approximations of block-structured matrices (e.g., block Hankel) using KRPs. We also develop new algorithms to accelerate tensor computations in the Tucker format using KRPs, and give theoretical guarantees of the resulting low-rank approximations. Numerical experiments on synthetic and real-world tensors show the computational benefits of the proposed methods.