Geometry and Symmetry in Short-and-Sparse Deconvolution-猫眼课题宝

DOI：

10.1137/19m1237569

发表时间：

2019-01

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Han-Wen Kuo;Yenson Lau;Yuqian Zhang;John Wright

我们研究从卷积中恢复短信号$\mathbf a_0$和稀疏信号$\mathbf x_0$的$\textit{短且稀疏（SaS）反卷积}$问题。我们提出一种基于非凸优化的方法，该方法在某些条件下能够恢复目标短信号和稀疏信号，但存在此模型固有的符号移位对称性。这种对称性在塑造反卷积的优化格局中起着核心作用。我们给出一种$\textit{区域分析}$，它在子空间的并集上从几何角度描述了这种格局。当长度为$p_0$的短信号$\mathbf a_0$具有移位相干性$\mu$，且$\mathbf x_0$遵循稀疏率为$\theta \in \Bigl[\frac{c_1}{p_0}, \frac{c_2}{p_0\sqrt\mu + \sqrt{p_0}}\Bigr]\cdot\frac{1}{\log^2p_0}$的随机稀疏模型时，我们的几何特征成立。基于这种几何结构，我们给出一种可证明的方法，该方法大概率能成功解决SaS反卷积问题。

We study the $\textit{Short-and-Sparse (SaS) deconvolution}$ problem of recovering a short signal $\mathbf a_0$ and a sparse signal $\mathbf x_0$ from their convolution. We propose a method based on nonconvex optimization, which under certain conditions recovers the target short and sparse signals, up to a signed shift symmetry which is intrinsic to this model. This symmetry plays a central role in shaping the optimization landscape for deconvolution. We give a $\textit{regional analysis}$, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-$p_0$ short signal $\mathbf a_0$ has shift coherence $\mu$, and $\mathbf x_0$ follows a random sparsity model with sparsity rate $\theta \in \Bigl[\frac{c_1}{p_0}, \frac{c_2}{p_0\sqrt\mu + \sqrt{p_0}}\Bigr]\cdot\frac{1}{\log^2p_0}$. Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.

Geometry and Symmetry in Short-and-Sparse Deconvolution

文献摘要

相似文献