Source-linked AI summary
Blind Deconvolution using Convex Programming
Ali Ahmed, Benjamin Recht, Justin Romberg
TL;DR
The paper addresses separating two unknown signals from their convolution under known-subspace structure. It recasts the problem as low-rank matrix recovery and shows that nuclear norm minimization can exactly deconvolve generic signals under incoherence and random-subspace conditions.
Problem
Separating two unknown signals from their convolution is non-unique without structural assumptions, motivating recovery under known subspaces.
Method
The paper lifts convolution into linear recovery of the rank-1 outer-product matrix and applies nuclear norm minimization using Fourier-domain constraints.
Results
Under Fourier incoherence for the fixed subspace and a generic random subspace for the other, nuclear norm minimization recovers both signals exactly up to scale with high probability.
Takeaways & Limitations
Known subspace structure makes blind deconvolution tractable by convex programming for relatively large subspace dimensions.
Takeaways & Limitations
The paper analyzes recovery only by nuclear norm minimization, while extensions to other effective recovery techniques remain possible rather than established.
Abstract
from arXiv · showhide
We consider the problem of recovering two unknown vectors, $\boldsymbol{w}$ and $\boldsymbol{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 $\boldsymbol{w}$ and $\boldsymbol{x}$, it is linear in the rank-1 matrix formed by their outer product $\boldsymbol{w}\boldsymbol{x}^*$. 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 $\boldsymbol{w}$ and $\boldsymbol{x}$ exactly when the maximum of $N$ and $K$ is almost on the order of $L$. That is, we show that if $\boldsymbol{x}$ is drawn from a random subspace of dimension $N$, and $\boldsymbol{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 $\boldsymbol{w}\boldsymbol{x}^*$ 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\times 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\gtrsim N+K$, to within constant and log factors.
1 Introduction
The paper reformulates blind deconvolution as nuclear norm minimization over a rank-1 matrix, establishing exact recovery under generic-subspace and Fourier-incoherence conditions. It also gives stability guarantees, empirical support, and an application to blind channel estimation.
- Problem: Blind deconvolution separates two unknown convolved signals using known subspaces of dimensions K and N.Without structural assumptions, the separation need not be unique; subspace structure can enable tractable convex recovery.
- Matrix formulation: The convolution is nonlinear in the signal coefficients but linear in their outer product X0 = hm*, yielding a linear inverse problem for a rank-1 matrix.This lifting step converts recovery of w and x into recovery of a K × N matrix.
- Convex relaxation: Nuclear norm minimization uses Fourier-domain constraints as a convex relaxation for recovering the lifted matrix.The approach builds on low-rank matrix recovery results for underdetermined linear observations.
- Main results: Exact recovery holds with high probability when B is Fourier-incoherent and C is a generic Gaussian subspace, under the dimensions and coherence conditions of Theorem 1.The recovered matrix is X0, allowing w and x to be recovered up to a scalar multiple with probability 1 − O(L^(-α+1)).
- Main results: When coherence parameters are constant-order, the dimensional condition is tight up to a logarithmic factor because max(K, N) ≤ L.The paper also reports stable recovery under noise and empirical success in settings including image deblurring.
- Application: For channel protection, a random code can estimate an unknown channel from one transmitted codeword when L/log^3 L is at least on the order of K + N.The channel model uses known path locations and a response that is relatively flat in frequency.
- Scope: The main theorem analyzes structured multi-Toeplitz operators for rank-1 recovery, while extensions to general low-rank recovery and other algorithms remain outside this paper’s scope.The authors note that guarantees might extend to alternative recovery techniques but do not establish those extensions here.
2 Numerical Simulations
Numerical experiments evaluate scalability, phase transitions, noise robustness, and image-deblurring applications of the blind deconvolution program. The experiments show high success under specified dimension conditions, decreasing error with oversampling, and recovery of images and blur kernels.
- Experimental scope: Large-scale experiments evaluate phase diagrams, image deblurring, and robustness to additive noise.The study includes problems with thousands or tens of thousands of unknown variables and uses computational methods for solving the associated programs.
- Optimization: The implemented factorized solver reformulates the semidefinite program using H and M, with r = 2 used to avoid non-global local solutions.The substitution automatically satisfies the semidefinite constraint; the resulting nonlinear program uses the measurement operator and its adjoint efficiently.
- Phase transitions: L ≳ 2.7(K + N) yields a high success rate for generic sparse or short w with Gaussian-subspace x at L = 2048.The experiments vary N and K across 100 random trials for each setting, using Gaussian expansion coefficients.
- Noise robustness: As L increases relative to N + K, recovery error decreases at fixed SNR; error also varies linearly with SNR on a log-log scale.The noisy experiments use L = 2048, N = 500, K = 250 and average results over 100 independent iterations.
- Image deblurring: The Shapes image is deblurred using a 65-pixel-support kernel, with experiments using both oracle and estimated wavelet supports.The oracle setup uses 5000 Haar-wavelet coefficients capturing 99.9% of image energy, while the non-oracle setup estimates a 9000-coefficient support from the blurred image.
3 Proof of main theorems
The proof establishes exact recovery by constructing a dual certificate for the rank-1 solution and controlling the associated random measurement operator. A golfing-scheme construction, concentration bounds, and conditioning results yield high-probability recovery conditions.
- Dual certificate: The main proof constructs a valid dual certificate showing that X0 = hm* uniquely minimizes the nuclear norm program.The certificate lies in Range(A*) and satisfies an inequality for every Z in Null(A).
- Dual certificate: The tangent subspace T associated with X0 = hm* and its projections PT and PT⊥ organize the recovery argument.The projection operators are defined using the rank-1 factors h and m.
- Golfing scheme: The golfing scheme divides the L observations into P disjoint subsets of size Q and uses them iteratively to construct Y.The iterates start at Y0 = 0, and the final certificate YP is shown to satisfy the required conditions with high probability.
- Golfing scheme: 2^-p bounds the residual norm after p golfing iterations, with probability exceeding 1 − 3L^-α+1.This geometric decay establishes the first required certificate condition.
- High-probability guarantees: Both certificate conditions hold with probability exceeding 1 − O(L^-α+1) when M is chosen according to the stated coherence-dependent condition.The same conditions also ensure that A*A is well conditioned on T.
- Operator conditioning: The operator lemmas control singular values of A and show that A is well conditioned on T under sufficiently underdetermined sampling.The proof uses random-matrix decompositions and Chernoff-like bounds for AA*.
4 Concentration inequalities
This section introduces scalar, vector, and matrix concentration tools for bounding random quantities in the recovery proof. Orlicz-1 norms and Bernstein-type inequalities provide tail bounds for sums of subexponential variables and matrices.
- Orlicz norms: The section characterizes subexponential random vectors and matrices using the Orlicz-1 norm.The norm connects tail behavior with bounds needed for later concentration estimates.
- Scalar concentration: Scalar Bernstein bounds control sums of independent centered subexponential random variables.The resulting probability bound decays exponentially in the deviation parameter.
- Matrix concentration: Matrix Bernstein bounds control sums of independent centered random matrices through their Orlicz norms and variance parameters.The result applies to K × N matrices and yields high-probability operator-norm bounds.
- Matrix concentration: A matrix Chernoff bound controls eigenvalues of sums of independent positive symmetric matrices.This tool is used later to bound both the upper and lower eigenvalues of AA*.
5 Proof of key lemmas
The key lemmas establish concentration and conditioning properties for the measurement operator and its golfing-scheme blocks. Their proofs decompose operators into independent random terms and apply Bernstein- and Chernoff-type bounds.
- Operator conditioning: The proof represents AA* as a sum of independent random matrices and applies a matrix Chernoff argument to bound its eigenvalues.Conditioning on bounded Fourier coefficients enables the required concentration analysis.
- Conditioning on T: The partial operators Ap are analyzed on T by decomposing PT(Ak) ⊗ PT(Ak) into four rank-1 tensor-product terms.Each term is controlled through expectations, Orlicz norms, variance calculations, and matrix Bernstein bounds.
- Conditioning on T: The four termwise estimates combine to give high-probability operator-norm concentration for the partial operators.The argument uses t = α log L and obtains failure probabilities of order L^-α for the component bounds.
- Golfing residual: The resulting bounds establish geometric contraction of the golfing residual and the second dual-certificate condition with high probability.The construction uses the partitioned operators Ap and an appropriate choice of Q and M.
- Golfing residual: The golfing residual Wp is rewritten as sums of independent random vectors or rank-1 matrices and bounded using scalar and matrix Bernstein inequalities.Union bounds over sample indices and golfing stages produce the stated probability guarantees.
6 Supporting Lemmas
The supporting lemmas derive the distributional and moment bounds needed for concentration arguments involving Gaussian Fourier-domain vectors. These results control scalar products, products of scalar products, and random matrix terms.
- Gaussian identities: For a Gaussian vector ĉk and arbitrary u, |⟨ĉk,u⟩|^2 has a chi-square distribution with two degrees of freedom.This distributional fact supplies tail and moment estimates used throughout the proof.
- Moment calculations: The supporting calculations determine expectations of products of Gaussian coordinates and show that off-diagonal terms vanish under the stated phase properties.These identities yield the expectations needed for random matrix variance calculations.
- Product bounds: Products ⟨ĉk,v⟩⟨u,ĉk⟩ receive tail bounds by splitting the event across the two Gaussian inner products.This supports control of cross terms appearing in the operator estimates.