期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 60, 期 3, 页码 1711-1732出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2013.2294644
关键词
Blind deconvolution; matrix factorizations; low-rank matrix; compressed sensing; channel estimation; rank-1 matrix; image deblurring; convex programming; nuclear norm minimization
资金
- ONR [N00014-11-1-0459, N00014-11-1-0723]
- Packard Foundation
- National Science Foundation [CCF-1139953, CCF-1148243]
- Direct For Computer & Info Scie & Enginr [1359814] Funding Source: National Science Foundation
- Division of Computing and Communication Foundations [1359814] Funding Source: National Science Foundation
We consider the problem of recovering two unknown vectors, w and x, of length L from their circular convolution. We make the structural assumption that the two vectors are members of known subspaces, one with dimension N and the other with dimension K. Although the observed convolution is nonlinear in both w and x, it is linear in the rank-1 matrix formed by their outer product wx*. This observation allows us to recast the deconvolution problem as low-rank matrix recovery problem from linear measurements, whose natural convex relaxation is a nuclear norm minimization program. We prove the effectiveness of this relaxation by showing that, for generic signals, the program can deconvolve w and x exactly when the maximum of N and K is almost on the order of L. That is, we show that if x is drawn from a random subspace of dimension N, and w is a vector in a subspace of dimension K whose basis vectors are spread out in the frequency domain, then nuclear norm minimization recovers wx* without error. We discuss this result in the context of blind channel estimation in communications. If we have a message of length N, which we code using a random L x N coding matrix, and the encoded message travels through an unknown linear time-invariant channel of maximum length K, then the receiver can recover both the channel response and the message when L greater than or similar to N + K, to within constant and log factors.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据