Low rank matrix recovery from Clifford orbits
Low rank matrix recovery from Clifford orbits
复制标题
从 Clifford 轨道恢复低阶矩阵
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Gross
中科院分区：
文献类型：
--
作者：
R. Kueng;Huangjun Zhu;D. Gross
我们证明，可以从从特定矩阵组的轨道采样的少量测量中有效地恢复低秩矩阵。作为一个特例，我们的理论对相位恢复问题进行了陈述。这里，任务是在仅给出其内积与来自轨道的少量向量的幅度的情况下恢复向量。该群的变体在数学的许多领域中以不同的名称出现。在编码理论和量子信息中，它是复Clifford群；在时频分析中，振荡器组；以及数学物理学中的元波群。它提供了一种特别小且高度结构化的轨道，该轨道包括并概括了离散傅立叶基：虽然傅立叶矢量具有与其索引线性相关的恒模系数和相位，但所述轨道中的矢量具有具有二次相关性的相位。在量子信息中，轨道被广泛使用，被称为稳定器状态集。我们认为，由于其丰富的几何结构和接近最佳的恢复特性，稳定态形成了相位恢复结构化测量的理想模型。我们的结果适用于 $m\geq C \kappa_r r d \log(d)$ 测量，其中过采样因子 k 根据轨道在 $\kappa_r=1$ 和 $\kappa_r = r^2$ 之间变化。重建对于加性噪声和低秩假设的偏差都是稳定的。如果感兴趣的矩阵另外是正半定的，则可以通过简单的约束最小二乘回归来执行重建。我们的证明方法可以适应其他群体的轨道。
We prove that low-rank matrices can be recovered efficiently from a small number of measurements that are sampled from orbits of a certain matrix group. As a special case, our theory makes statements about the phase retrieval problem. Here, the task is to recover a vector given only the amplitudes of its inner product with a small number of vectors from an orbit. Variants of the group in question have appeared under different names in many areas of mathematics. In coding theory and quantum information, it is the complex Clifford group; in time-frequency analysis the oscillator group; and in mathematical physics the metaplectic group. It affords one particularly small and highly structured orbit that includes and generalizes the discrete Fourier basis: While the Fourier vectors have coefficients of constant modulus and phases that depend linearly on their index, the vectors in said orbit have phases with a quadratic dependence. In quantum information, the orbit is used extensively and is known as the set of stabilizer states. We argue that due to their rich geometric structure and their near-optimal recovery properties, stabilizer states form an ideal model for structured measurements for phase retrieval. Our results hold for $m\geq C \kappa_r r d \log(d)$ measurements, where the oversampling factor k varies between $\kappa_r=1$ and $\kappa_r = r^2$ depending on the orbit. The reconstruction is stable towards both additive noise and deviations from the assumption of low rank. If the matrices of interest are in addition positive semidefinite, reconstruction may be performed by a simple constrained least squares regression. Our proof methods could be adapted to cover orbits of other groups.
影响因子：
1.2
作者：
V. Pohl;Fanny Yang;H. Boche
通讯作者：
V. Pohl;Fanny Yang;H. Boche