The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Blind Deconvolution Using Convex Programming
Abstract
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 ≳ N + K, to within constant and log factors.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Weak Convergence and Empirical Processes
van der Vaart, A. W., & Wellner, J. A. (1996) · Springer Series in Statistics · doi:10.1007/978-1-4757-2545-2 · Cited by 5,014
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Self-citationGuaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Self-citationSparsity and incoherence in compressive sampling
Candès, E., & Romberg, J. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,075
Self-citationThe Power of Convex Relaxation: Near-Optimal Matrix Completion
Candes, E. J., & Tao, T. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2044061 · Cited by 2,060
Candes, E. J., & Plan, Y. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2035722 · Cited by 1,709
Kundur, D., & Hatzinakos, D. (1996) · IEEE Signal Processing Magazine · doi:10.1109/79.489268 · Cited by 1,275
Total variation blind deconvolution
Chan, T. F., & Wong, C.-K. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.661187 · Cited by 1,201
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candès, E. J., Strohmer, T., & Voroninski, V. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21432 · Cited by 1,197
Cited by
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
Self-citationNonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
“Known relaxations [42], [48] fix the scale by setting (cid:107) q ∗ Y ∞ = 1 and use (cid:107)·(cid:107) 1 as a surrogate to (cid:107)·(cid:107) 0 , where (cid:107)·(cid:107) ∞ is the elementwise ∞ norm, leading to the optimization problem The constraint means at least one coordinate of q ∗ Y has…”
BackgroundNonconvex Demixing From Bilinear Measurements
Dong, J., & Shi, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2864660 · Cited by 37
“Although blind demixing can be regarded as a variant of blind deconvolution [7] by extending the problem of “single-source” setting to the “multi-source” setting, it is nontrivial to accomplish the extension.”
Blind Demixing for Low-Latency Communication
Dong, J., Yang, K., & Shi, Y. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2018.2886191 · Cited by 22
Fast Weighted Total Variation Regularization Algorithm for Blur Identification and Image Restoration
Liu, H., Gu, J., Meng, M. Q.-H., & Lu, W.-S. (2016) · IEEE Access · doi:10.1109/access.2016.2516949 · Cited by 16
Metadata
- Authors
- Ahmed, A., Recht, B., & Romberg, J.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2014-03
- Volume
- 60
- Issue
- 3
- Pages
- 1711-1732
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2140867429
- Cited by
- 387
- References
- 36
- FWCI
- 34.24
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.