Stable Signal Recovery from Phaseless Measurements

The aim of this paper is to study the stability of the \(\ell _1\) minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that \(m={\mathcal {O}}(k\log (N/k))\) measurements are enough to guarantee the \(\ell _1\) minimization to recover k-sparse signals stably provided the measurement matrix A satisfies the strong RIP property. We second investigate the phaseless instance-optimality presenting a null space property of the measurement matrix A under which there exists a decoder \(\Delta \) so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the \(\ell _1\) norm. This builds a parallel for compressive phase retrieval with the classical compressive sensing.     

Stable Optimizationless Recovery from Phaseless Linear Measurements

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(nlogn) 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.     

Exact Matrix Completion via Convex Optimization

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $m\ge C\,n^{1.2}r\log n$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.     

Exact Penalty Functions for Convex Bilevel Programming Problems

In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given.     

Generalized Convex Multiplicative Programming via Quasiconcave Minimization

We present a new method for minimizing the sum of a convex function and aproduct of k nonnegative convex functions over a convex set. This problem isreduced to a k-dimensional quasiconcave minimization problem which is solvedby a conical branch-and-bound algorithm. Comparative computational results areprovided on test problems from the literature.     

Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by Stubbs and Mehrotra [21] and Ceria and Soares [6], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a Mixed-Integer Nonlinear Programming (MINLP) problem that is shown to be tighter than the conventional big-M formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.     

Convex Variational Formulation with Smooth Coupling for Multicomponent Signal Decomposition and Recovery

A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces. The cost function consists of a separable term, in which each component is modeled through its own potential, and of a coupling term, in which constraints on linear transformations of the components are penalized with smooth functionals. An algorithm with guaranteed weak convergence to a solution to the problem is provided. Various multicomponent signal decomposition and recovery applications are discussed.     

凸体截面的稳定性

证明了如果两个凸体被过原点的任何一个超平面所截得到的截面具有相等的平均弦长和相同的对偶Steiner点,则这两个凸体是重合的,并且得到此定理的一个的稳定性版本.     

ShapeFit: Exact Location Recovery from Corrupted Pairwise Directions

Let t₁,…,t_n ∊ ℝ^d for d ≥ 2 and consider the location recovery problem: given a subset of pairwise direction observations , where a constant fraction of these observations are arbitrarily corrupted, find up to a global translation and scale. We propose a novel algorithm for the location recovery problem, which consists of a simple convex program over $dn$ real variables. We prove that this program recovers a set of n i.i.d. Gaussian locations exactly and with high probability if the observations are given by an Erdős‐Rényi graph, with d large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. We also prove that the program exactly recovers Gaussian locations for d = 3 if the fraction of corrupted observations at each location is, up to poly‐logarithmic factors, at most a constant. Both of these recovery theorems are based on a set of deterministic conditions that we prove are sufficient for exact recovery. © 2017 Wiley Periodicals, Inc.     

Sparse Recovery from Inaccurate Saturated Measurements

This article studies a variation of the standard compressive sensing problem, in which sparse vectors \(\mathbf{x}\in\mathbb{R}^{N}\) are acquired through inaccurate saturated measurements \(\mathbf{y}= \mathcal{S}(\mathbf {A}\mathbf{x}+ \mathbf{e}) \in\mathbb{R}^{m}\), \(m \ll N\). The saturation function \(\mathcal{S}\) acts componentwise by sending entries that are large in absolute value to plus-or-minus a threshold while keeping the other entries unchanged. The present study focuses on the effect of the presaturation error \(\mathbf{e}\in\mathbb{R}^{m}\). The existing theory for accurate saturated measurements, i.e., the case \(\mathbf{e}= \mathbf{0}\), which exhibits two regimes depending on the magnitude of \(\mathbf{x}\in\mathbb {R}^{N}\), is extended here. A recovery procedure based on convex optimization is proposed and shown to be robust to presaturation error in both regimes. Another procedure ignoring the presaturation error is also analyzed and shown to be robust in the small magnitude regime.     

Stable Determination of Convex Bo dies from Intersection Bo dies

In this paper, by means of the dual Brunn-Minkowski theories and methods as well as the integral transform, we have established a stability version of nonsymmetric convex bodies from intersection bodies. In addition, a stability results of symmetric convex bodies from Lp-counterparts is established.     

Penalty and Barrier Methods for Convex Semidefinite Programming

In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.     

基于非凸优化模型的块稀疏信号恢复条件

压缩感知(compressed sensing,CS)是一种全新的信息采集与处理理论，它表明稀疏信号能够在远低于Shannon-Nyquist采样率的条件下被精确重构.现从压缩感知理论出发，对块稀疏信号重构算法进行研究，通过混合l₂/l_q(0相似文献   

Generalized Semi-Infinite Programming: Optimality Conditions Involving Reverse Convex Problems

This article deals with a generalized semi-infinite programming problem (S). Under appropriate assumptions, for such a problem we give necessary and sufficient optimality conditions via reverse convex problems. In particular, a necessary and sufficient optimality condition reduces the problem (S) to a min-max problem constrained with compact convex linked constraints.     

Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares

In countless applications, we need to reconstruct a $K$-sparse signal $\mathbf{x}\in\mathbb{R}^n$ from noisy measurements $\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{v}$, where $\mathbf{\Phi}\in\mathbb{R}^{m\times n}$ is a sensing matrix and $\mathbf{v}\in\mathbb{R}^m$ is a noise vector. Orthogonal least squares (OLS), which selects at each step the column that results in the most significant decrease in the residual power, is one of the most popular sparse recovery algorithms. In this paper, we investigate the number of iterations required for recovering $\mathbf{x}$ with the OLS algorithm. We show that OLS provides a stable reconstruction of all $K$-sparse signals $\mathbf{x}$ in $\lceil2.8K\rceil$ iterations provided that $\mathbf{\Phi}$ satisfies the restricted isometry property (RIP). Our result provides a better recovery bound and fewer number of required iterations than those proposed by Foucart in 2013.     

Stable and Total Fenchel Duality for Composed Convex Optimization Problems

In this paper, we consider the composed convex optimization problem which consists in minimizing the sum of a convex function and a convex composite function. By using the properties of the epigraph of the conjugate functions and the subdifferentials of convex functions, we give some new constraint qualifications which completely characterize the strong Fenchel duality and the total Fenchel duality for composed convex optimiztion problem in real locally convex Hausdorff topological vector spaces.     

凸二次规划问题逆问题的模型与解法

本文分别考虑带非负约束和不带大量负约束凸二次规划问题逆问题。首先得到各个逆问题的数学模型,然后对不同的模型给出不同的求解方法。