Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions
Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions
复制标题
最小假设下盲解卷积的可识别性和稳定性
DOI：
--
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
Y. Bresler
中科院分区：
文献类型：
--
作者：
Yanjun Li;Kiryung Lee;Y. Bresler
在许多应用中出现了盲反卷积（BD）。没有关于信号和过滤器的假设，BD不接受唯一的解决方案。实际上，子空间或稀疏假设表明能够减少搜索空间并产生独特的解决方案。但是，关于BD中唯一性的现有理论分析是相当有限的。在较早的论文中，我们为BD提供了第一个代数样本复杂性，该复杂性几乎所有基地或框架都为Lebesgue提供。我们表明，对于<inline-formula> <tex-math notegy =“ latex”> $ \ mathbb {c}^{n} $ </tex-math> </inline-formula>，具有尺寸的子空间约束<inline-formula> <tex-math notegy =“ latex”> $ m_ {1} $在<inline-formula> <tex-math notegy的样本复杂性=“ latex”> $ n \ geq m_ {1} m_ {2} $ </tex-math> </inline-formula>就足够了。此结果是次优的，因为自由度的数量仅仅是<inline-formula> <tex-math notegy =“ latex”> $ m_ {1}+m_ {2} -1 $ </tex-math> </</内联式>。我们为BD提供了稀疏性或混合子空间和稀疏性约束的BD的类似结果。在本文中，利用了在独特的低级别矩阵恢复的信息理论限制上的最新进展，我们终于弥合了此间隙，并获得了具有通用碱基或帧的BD的最佳样本复杂性结果。我们表明，对于<inline-formula> <tex-math notegy =“ latex”> $ \ mathbb {c} ^{c} ^{n} $ </tex-math>，对于<inline-formula> <inline-formula> <inline-formula> <tex-math notegy> <inline-formula> <tex-math notege> bd（分别是所有对）的bd。 </inline-formula>，具有稀疏级别的稀疏性约束<inline-formula> <tex-math notegement =“ latex”> $ s_ {1} $ </tex-math> </inline-formula>和<inline-formula> <tex-math notegy =“ latex”> $ s_ {2} $ </tex-math> </inline-formula>，样本复杂性<inline-formula> <tex-math notege =“ latex”> $ n> s_ {1}+s_ {2} $ </tex-math> </inline-formula> [分别，<inline-formula> <tex-math notegy =“ latex”> $ n> 2（s_ {1}+s_ {2}）$ </tex-math> </inline-formula>]就足够了。我们还为BD提供了类似的结果，该结果具有子空间约束或混合约束，子空间维度取代了稀疏度。最后但并非最不重要的一点是，在上述所有情况下，如果碱基或帧遵循本文指定的概率分布，则恢复不仅是唯一的，而且在相同的样本复杂性下对测量中的小扰动也稳定。
Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in <inline-formula> <tex-math notation="LaTeX">$ \mathbb {C}^{n}$ </tex-math></inline-formula>, with subspace constraints of dimensions <inline-formula> <tex-math notation="LaTeX">$m_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$m_{2}$ </tex-math></inline-formula>, respectively, a sample complexity of <inline-formula> <tex-math notation="LaTeX">$n\geq m_{1}m_{2}$ </tex-math></inline-formula> is sufficient. This result is suboptimal, since the number of degrees of freedom is merely <inline-formula> <tex-math notation="LaTeX">$m_{1}+m_{2}-1$ </tex-math></inline-formula>. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in <inline-formula> <tex-math notation="LaTeX">$ \mathbb {C} ^{n}$ </tex-math></inline-formula>, with sparsity constraints of sparsity levels <inline-formula> <tex-math notation="LaTeX">$s_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$s_{2}$ </tex-math></inline-formula>, a sample complexity of <inline-formula> <tex-math notation="LaTeX">$n > s_{1}+s_{2}$ </tex-math></inline-formula> [respectively, <inline-formula> <tex-math notation="LaTeX">$n > 2(s_{1}+s_{2})$ </tex-math></inline-formula>] is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.