The design of high-precision sensing devises becomes ever more difficult and expensive. At the same time, the need for precise calibration of these devices (ranging from tiny sensors to space telescopes) manifests itself as a major roadblock in many scientific and technological endeavors. To achieve optimal performance of advanced high-performance sensors one must carefully calibrate them, which is often difficult or even impossible to do in practice. In this work we bring together three seemingly unrelated concepts, namely self-calibration, compressive sensing, and biconvex optimization. The idea behind self-calibration is to equip a hardware device with a smart algorithm that can compensate automatically for the lack of calibration. We show how several self-calibration problems can be treated efficiently within the framework of biconvex compressive sensing via a new method called SparseLift. More specifically, we consider a linear system of equations where both and the diagonal matrix (which models the calibration error) are unknown. By 'lifting' this biconvex inverse problem we arrive at a convex optimization problem. By exploiting sparsity in the signal model, we derive explicit theoretical guarantees under which both and can be recovered exactly, robustly, and numerically efficiently via linear programming. Applications in array calibration and wireless communications are discussed and numerical simulations are presented, confirming and complementing our theoretical analysis.
This idea of "Lifting" also applies to blind deconvolution @cite_44 , which refers to the recovery of two unknown signals from their convolution. The model can be converted into the form via applying the Fourier transform and under proper assumptions @math can be recovered exactly by solving a nuclear norm minimization program in the following form, if the number of measurements is at least larger than the dimensions of both @math and @math . Compared with PhaseLift , the difference is that @math can be asymmetric and there is of course no guarantee for positivity. Ahmed, Recht, and Romberg derived a very appealing framework for blind deconvolution via convex programming, and we borrow many of their ideas for our proofs.
@cite_44
2140867429 2963131734 2430435693 1605194072
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. Recovering an unknown complex signal from the magnitude of linear combinations of the signal is referred to as phase retrieval. We present an exact performance analysis of a recently proposed convex-optimization-formulation for this problem, known as PhaseMax. Standard convex-relaxation-based methods in phase retrieval resort to the idea of “lifting” which makes them computationally inefficient, since the number of unknowns is effectively squared. In contrast, PhaseMax is a novel convex relaxation that does not increase the number of unknowns. Instead it relies on an initial estimate of the true signal which must be externally provided. In this paper, we investigate the required number of measurements for exact recovery of the signal in the large system limit and when the linear measurement matrix is random with iid standard normal entries. If @math denotes the dimension of the unknown complex signal and @math the number of phaseless measurements, then in the large system limit, @math measurements is necessary and sufficient to recover the signal with high probability, where @math is the angle between the initial estimate and the true signal. Our result indicates a sharp phase transition in the asymptotic regime which matches the empirical result in numerical simulations. We study the question of reconstructing two signals @math and @math from their convolution @math . This problem, known as blind deconvolution , pervades many areas of science and technology, including astronomy, medical imaging, optics, and wireless communications. A key challenge of this intricate non-convex optimization problem is that it might exhibit many local minima. We present an efficient numerical algorithm that is guaranteed to recover the exact solution, when the number of measurements is (up to log-factors) slightly larger than the information-theoretical minimum, and under reasonable conditions on @math and @math . The proposed regularized gradient descent algorithm converges at a geometric rate and is provably robust in the presence of noise. To the best of our knowledge, our algorithm is the first blind deconvolution algorithm that is numerically efficient, robust against noise, and comes with rigorous recovery guarantees under certain subspace conditions. Moreover, numerical experiments do not only provide empirical verification of our theory, but they also demonstrate that our method yields excellent performance even in situations beyond our theoretical framework. Consider the recovery of an unknown signal @math from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that @math is sparse, and that the measurements are of the form @math . Since such measurements give no information on the norm of @math , recovery methods typically assume that @math . We show that if one allows more generally for quantized affine measurements of the form @math , and if the vectors @math are random, an appropriate choice of the affine shifts @math allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. In addition, we show that for arbitrary fixed @math in the annulus @math , one may estimate the norm @math up to additive error @math from @math such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors @math in a Euclidean ball of known radius.