论文标题
可证明的近距离低型量张量恢复
Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
论文作者
论文摘要
我们考虑从少量线性测量值中恢复低变量量张量的问题。 We show that the Riemannian gradient algorithm initialized by one step of iterative hard thresholding can reconstruct an order-$d$ tensor of size $n\times\ldots\times n$ and multilinear rank $(r,\ldots,r)$ with high probability from only $O(nr^2 + r^{d+1})$ measurements, assuming $d$ is a constant.与现有的结果相比，这种抽样复杂性在$ n $中是最佳的，这些结果在$ n $中都不必要地大。该分析依赖于张量限制的等轴测特性（TRIP）和具有固定多线性等级的所有张量的歧管的几何形状。我们的算法的高计算效率也可以通过对仅$ 2R \ times \ ldots \ times 2r $的中间小张量进行更高级奇异的值分解来实现，而不是对大小$ n \ times \ times \ ldots \ ldots \ ldots \ ldots \ ldots \ ldots \ times n $的张力。
We consider the problem of recovering a low-multilinear-rank tensor from a small amount of linear measurements. We show that the Riemannian gradient algorithm initialized by one step of iterative hard thresholding can reconstruct an order-$d$ tensor of size $n\times\ldots\times n$ and multilinear rank $(r,\ldots,r)$ with high probability from only $O(nr^2 + r^{d+1})$ measurements, assuming $d$ is a constant. This sampling complexity is optimal in $n$, compared to existing results whose sampling complexities are all unnecessarily large in $n$. The analysis relies on the tensor restricted isometry property (TRIP) and the geometry of the manifold of all tensors with a fixed multilinear rank. High computational efficiency of our algorithm is also achieved by doing higher order singular value decomposition on intermediate small tensors of size only $2r\times \ldots\times 2r$ rather than on tensors of size $n\times \ldots\times n$ as usual.
