@article{Ahmed2012,
abstract = {We consider the problem of recovering two unknown vectors, \$\backslash w\$ and \$\backslash 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 \$\backslash w\$ and \$\backslash x\$, it is linear in the rank-1 matrix formed by their outer product \$\backslash w\backslash 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 \$\backslash w\$ and \$\backslash x\$ exactly when the maximum of \$N\$ and \$K\$ is almost on the order of \$L\$. That is, we show that if \$\backslash x\$ is drawn from a random subspace of dimension \$N\$, and \$\backslash 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 \$\backslash w\backslash 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\backslash 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\backslash gtrsim N+K\$, to within constant and log factors.},
archivePrefix = {arXiv},
arxivId = {1211.5608},
author = {Ahmed, Ali and Recht, Benjamin and Romberg, Justin},
eprint = {1211.5608},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/blind\_deconv\_SDP.pdf:pdf},
journal = {arXiv preprint arXiv:1211.5608},
month = nov,
pages = {40},
title = {{Blind deconvolution using convex programming}},
url = {http://arxiv.org/abs/1211.5608},
year = {2012}
}
@article{Aravkin2013,
archivePrefix = {arXiv},
arxivId = {arXiv:1302.4886v2},
author = {Aravkin, AY and Kumar, Rajiv and Mansour, Hassan and Recht, B},
eprint = {arXiv:1302.4886v2},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/robust\_svd\_free.pdf:pdf},
pages = {1--20},
title = {{A robust SVD-free approach to matrix completion, with applications to interpolation of large scale data}},
url = {http://scholar.google.com/scholar?hl=en\&btnG=Search\&q=intitle:A+robust+svd-free+approach+to+matrix+completion,+with+applications+to+interpolation+of+large+scale+data\#0 http://scholar.google.com/scholar?hl=en\&btnG=Search\&q=intitle:A+robust+SVD-free+approach+to+matrix+completion,+with+applications+to+interpolation+of+large+scale+data\#0},
year = {2013}
}
@article{Burer2004,
author = {Burer, Samuel and Monteiro, Renato D.C.},
doi = {10.1007/s10107-004-0564-1},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/burer\_monteiro.pdf:pdf},
isbn = {1010700405},
issn = {0025-5610},
journal = {Mathematical Programming},
keywords = {augmented lagrangian,combinatorial opti-,low-rank matrices,mization,nonlinear programming,numerical experiments,semidefinite programming,vector programming},
month = dec,
number = {3},
pages = {427--444},
title = {{Local Minima and Convergence in Low-Rank Semidefinite Programming}},
url = {http://link.springer.com/10.1007/s10107-004-0564-1},
volume = {103},
year = {2004}
}
@article{Candes2013,
abstract = {Suppose we wish to recover a signal x in C\^{}n from m intensity measurements of the form |<x,z\_i>|\^{}2, i = 1, 2,..., m; that is, from data in which phase information is missing. We prove that if the vectors z\_i are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program---a trace-norm minimization problem; this holds with large probability provided that m is on the order of n log n, and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis a vis additive noise.},
archivePrefix = {arXiv},
arxivId = {http://arxiv.org/abs/1109.4499},
author = {Cand\`{e}s, Emmanuel J. and Strohmer, Thomas and Voroninski, Vladislav},
doi = {10.1002/cpa.21432},
eprint = {/arxiv.org/abs/1109.4499},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/ExactPR-3.pdf:pdf},
issn = {00103640},
journal = {Communications on Pure and Applied Mathematics},
month = aug,
number = {8},
pages = {1241--1274},
primaryClass = {http:},
title = {{PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming}},
url = {http://doi.wiley.com/10.1002/cpa.21432},
volume = {66},
year = {2013}
}
@article{Candes2010,
abstract = {On the heels of compressed sensing, a remarkable new field has very recently emerged. This field addresses a broad range of problems of significant practical interest, namely, the recovery of a data matrix from what appears to be incomplete, and perhaps even corrupted, information. In its simplest form, the problem is to recover a matrix from a small sample of its entries, and comes up in many areas of science and engineering including collaborative filtering, machine learning, control, remote sensing, and computer vision to name a few. This paper surveys the novel literature on matrix completion, which shows that under some suitable conditions, one can recover an unknown low-rank matrix from a nearly minimal set of entries by solving a simple convex optimization problem, namely, nuclear-norm minimization subject to data constraints. Further, this paper introduces novel results showing that matrix completion is provably accurate even when the few observed entries are corrupted with a small amount of noise. A typical result is that one can recover an unknown n x n matrix of low rank r from just about nr log\^{}2 n noisy samples with an error which is proportional to the noise level. We present numerical results which complement our quantitative analysis and show that, in practice, nuclear norm minimization accurately fills in the many missing entries of large low-rank matrices from just a few noisy samples. Some analogies between matrix completion and compressed sensing are discussed throughout.},
archivePrefix = {arXiv},
arxivId = {0903.3131},
author = {Candes, Emmanuel J and Plan, Yaniv},
doi = {10.1109/JPROC.2009.2035722},
eprint = {0903.3131},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/candes\_plan.pdf:pdf},
issn = {0018-9219},
journal = {Proceedings of the IEEE},
keywords = {com-,duality in optimization,low-rank matrices,matrix completion,nuclear-norm minimization,oracle inequalities,semidefinite programming},
month = jun,
number = {6},
pages = {925--936},
title = {{Matrix Completion With Noise}},
url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=5454406 http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5454406},
volume = {98},
year = {2010}
}
@article{Demanet2012,
abstract = {We address the problem of recovering an n-vector from m linear measurements lacking sign or phase information. We show that lifting and semidefinite relaxation suffice by themselves for stable recovery in the setting of m = O(n log n) random sensing vectors, with high probability. The recovery method is optimizationless in the sense that trace minimization in the PhaseLift procedure is unnecessary. That is, PhaseLift reduces to a feasibility problem. The optimizationless perspective allows for a Douglas-Rachford numerical algorithm that is unavailable for PhaseLift. This method exhibits linear convergence with a favorable convergence rate and without any parameter tuning.},
archivePrefix = {arXiv},
arxivId = {1208.1803},
author = {Demanet, Laurent and Hand, Paul},
eprint = {1208.1803},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/demanet.pdf:pdf},
journal = {arXiv preprint arXiv:1208.1803},
keywords = {15a83,65k05,90c22,ams classifications,douglas-rachford,feasibility,lifting,matrix completion,phase retrieval,phaselift,semidefinite relaxation},
month = aug,
pages = {1--20},
title = {{Stable optimizationless recovery from phaseless linear measurements}},
url = {http://arxiv.org/abs/1208.1803},
year = {2012}
}
@article{Demanet2013,
author = {Demanet, Laurent and Jugnon, Vincent},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/convex-interferometric.pdf:pdf},
journal = {arXiv preprint arXiv:1307.6864},
number = {July},
pages = {1--19},
title = {{Convex recovery from interferometric measurements}},
url = {http://arxiv.org/abs/1307.6864},
year = {2013}
}
@article{Fogel2013,
abstract = {We study convex relaxation algorithms for phase retrieval on imaging problems. We show that structural assumptions on the signal and the observations, such as sparsity, smoothness or positivity, can be exploited to both speed-up convergence and improve recovery performance. We detail experimental results in molecular imaging problems simulated from PDB data.},
author = {Fogel, Fajwel and Waldspurger, Ir\`{e}ne and D'Aspremont, a},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/DogPatch.pdf:pdf},
journal = {arXiv preprint arXiv:1304.7735},
keywords = {and phrases,fourier optics,molecular imaging,phase recovery,semidefinite programming,x-ray diffraction},
title = {{Phase retrieval for imaging problems}},
url = {http://arxiv.org/abs/1304.7735},
year = {2013}
}
@article{Hand,
author = {Hand, Paul},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/lifttest/hand\_sampta.pdf:pdf},
journal = {math.mit.edu},
pages = {372--375},
title = {{Conditions for Dual Certificate Existence in Semidefinite Rank-1 Matrix Recovery}},
url = {http://math.mit.edu/~hand/pubs/hand\_sampta.pdf}
}
@article{Lemarechal1999,
author = {Lemar\'{e}chal, C and Oustry, F},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/SDPlifting.pdf:pdf},
title = {{Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization}},
url = {http://hal.archives-ouvertes.fr/docs/00/07/29/58/PDF/RR-3710.pdf},
year = {1999}
}
@article{Li2001,
author = {Li, DH and Fukushima, M},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/10.1.1.47.8382.pdf:pdf},
journal = {SIAM Journal on Optimization},
keywords = {1999,and,available until october,bfgs method,department of applied mathematics,e-mail,global convergence,graduate school of informatics,japan,kyoto 606-8501,kyoto university,physics,present address,unconstrained optimization},
title = {{On the global convergence of the BFGS method for nonconvex unconstrained optimization problems}},
url = {http://epubs.siam.org/doi/pdf/10.1137/S1052623499354242},
year = {2001}
}
@article{Recht2010,
author = {Recht, Benjamin and Fazel, M and Parrilo, PA},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/guaranteed\_min\_rank\_solns.pdf:pdf},
journal = {SIAM review},
keywords = {compressed sensing,convex optimization,matrix norms,random matrices,rank,semidefinite program-},
pages = {1--32},
title = {{Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization}},
url = {http://epubs.siam.org/doi/abs/10.1137/070697835},
year = {2010}
}
@article{VanLeeuwen2013,
abstract = {Wave-equation based inversions, such as full-waveform inversion, are challenging because of their computational costs, memory requirements, and reliance on accurate initial models. To confront these issues, we propose a novel formulation of full-waveform inversion based on a penalty method. In this formulation, the objective function consists of a data-misfit term and a penalty term which measures how accurately the wavefields satisfy the wave-equation. Because we carry out the inversion over a larger search space, including both the model and synthetic wavefields, our approach suffers less from local minima. Our main contribution is the development of an efficient optimization scheme that avoids having to store and update the wavefields by explicit elimination. Compared to existing optimization strategies for full-waveform inversion, our method differers in two main aspects; i) The wavefields are solved from an augmented wave-equation, where the solution is forced to solve the wave-equation and fit the observed data, ii) no adjoint wavefields are required to update the model, which leads to significant computational savings. We demonstrate the validity of our approach by carefully selected examples and discuss possible extensions and future research.},
author = {van Leeuwen, T. and Herrmann, F. J.},
file = {:D$\backslash$:/Dropbox/docs/math/SLIM/papers/vanLeeuwen2013Penalty1.pdf:pdf},
journal = {Geophysical Journal International},
keywords = {computa-,controlled source seismology,inverse theory,seismic tomography},
number = {1},
pages = {661--667},
title = {{Mitigating local minima in full-waveform inversion by expanding the search space}},
url = {http://gji.oxfordjournals.org/cgi/doi/10.1093/gji/ggt258},
volume = {195},
year = {2013}
}