论文标题
从矩阵矢量产物中恢复结构化基质
Structured matrix recovery from matrix-vector products
论文作者
论文摘要
一个人可以仅从矩阵矢量产物中有效恢复矩阵吗？如果是这样，需要多少？本文介绍了从矩阵 - 矢量产物中恢复具有已知结构的矩阵，例如tridiagonal，toeplitz，toeplitz，类似于Toeplitz，类似于Toeplitz，类似于Toeplitz的低级别。特别是，我们得出了一种随机算法，用于恢复$ n \ times n $未知的层次低排名矩阵，仅从$ \ nathcal {o}（（（k+p）\ log p）\ log（n））$ matrix-vector产品具有很高的可能性，其中$ k $是Off-Diagonal blocks and $ k $的排名我们通过仔细构建利用矩阵层次结构的矩阵向量产物的随机输入向量来做到这一点。尽管用于层次矩阵恢复的现有算法使用基于消除的递归“剥离”程序，但我们的方法使用了递归投影过程。
Can one recover a matrix efficiently from only matrix-vector products? If so, how many are needed? This paper describes algorithms to recover matrices with known structures, such as tridiagonal, Toeplitz, Toeplitz-like, and hierarchical low-rank, from matrix-vector products. In particular, we derive a randomized algorithm for recovering an $N \times N$ unknown hierarchical low-rank matrix from only $\mathcal{O}((k+p)\log(N))$ matrix-vector products with high probability, where $k$ is the rank of the off-diagonal blocks, and $p$ is a small oversampling parameter. We do this by carefully constructing randomized input vectors for our matrix-vector products that exploit the hierarchical structure of the matrix. While existing algorithms for hierarchical matrix recovery use a recursive "peeling" procedure based on elimination, our approach uses a recursive projection procedure.
