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.
Besides drawing from general ideas in compressive sensing and matrix completion, the research presented in this work is mostly influenced by papers related to PhaseLift @cite_43 @cite_23 @cite_10 and in particular by the very inspiring paper on blind deconvolution by Ahmed, Recht, and Romberg @cite_44 . PhaseLift provides a strategy of how to reconstruct a signal @math from its quadratic measurements @math via lifting'' techniques. Here the key idea is to lift a vector-valued quadratic problem to a matrix-valued linear problem. Specifically, we need to find a rank-one positive semi-definite matrix @math which satisfies linear measurement equations of @math : @math where @math Generally problems of this form are NP-hard. However, solving the following nuclear norm minimization yields exact recovery of @math
@cite_44 @cite_43 @cite_10 @cite_23
2963131734 2140867429 2163973643 2963583445
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 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. Recent compressive sensing results show that it is possible to accurately reconstruct certain compressible signals from relatively few linear measurements via solving nonsmooth convex optimization problems. In this paper, we propose the use of the alternating direction method - a classic approach for optimization problems with separable variables (D. Gabay and B. Mercier, ?A dual algorithm for the solution of nonlinear variational problems via finite-element approximations,? Computer and Mathematics with Applications, vol. 2, pp. 17-40, 1976; R. Glowinski and A. Marrocco, ?Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires,? Rev. Francaise dAut. Inf. Rech. Oper., vol. R-2, pp. 41-76, 1975) - for signal reconstruction from partial Fourier (i.e., incomplete frequency) measurements. Signals are reconstructed as minimizers of the sum of three terms corresponding to total variation, ?1-norm of a certain transform, and least squares data fitting. Our algorithm, called RecPF and published online, runs very fast (typically in a few seconds on a laptop) because it requires a small number of iterations, each involving simple shrinkages and two fast Fourier transforms (or alternatively discrete cosine transforms when measurements are in the corresponding domain). RecPF was compared with two state-of-the-art algorithms on recovering magnetic resonance images, and the results show that it is highly efficient, stable, and robust. Abstract We study the recovery of Hermitian low rank matrices X ∈ C n × n from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form a j a j ⁎ for some measurement vectors a 1 , … , a m , i.e., the measurements are given by b j = tr ( X a j a j ⁎ ) . The case where the matrix X = x x ⁎ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements b j = | 〈 x , a j 〉 | 2 ) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors a j , j = 1 , … , m , being chosen independently at random according to a standard Gaussian distribution, or a j being sampled independently from an (approximate) complex projective t-design with t = 4 . In the Gaussian case, we require m ≥ C r n measurements, while in the case of 4-designs we need m ≥ Cr n log ⁡ ( n ) . Our results are uniform in the sense that one random choice of the measurement vectors a j guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.