A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers … Read more
We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more
In Riemannian optimization problems, commonly encountered manifolds are $d$-dimensional matrix manifolds whose tangent spaces can be represented by $d$-dimensional linear subspaces of a $w$-dimensional Euclidean space, where $w > d$. Therefore, representing tangent vectors by $w$-dimensional vectors has been commonly used in practice. However, using $w$-dimensional vectors may be the most natural but may not … Read more
A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more
The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre, Toh, and Yang [EURO J. Comput. Optim., 2015] constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal value of the original … Read more
An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite {matrices} $\{P_i\}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}= {\rm Tr}(P_iP_j),$ for all $i,j \in \{ 1, \ldots, n \}$. The cpsd-rank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation … Read more
We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The employed Krylov subspace methods do not suffer from rank-deficiency and therefore no … Read more
We give new insight into the Grassmann condition of the conic feasibility problem \[ x \in L \cap K \setminus\{0\}. \] Here $K\subseteq V$ is a regular convex cone and $L\subseteq V$ is a linear subspace of the finite dimensional Euclidean vector space $V$. The Grassmann condition of this problem is the reciprocal of the … Read more
Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more
One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more