Let D be the set of density matrices, i.e., the set of positive definite matrices of unit trace. We show that any polytope P that is sandwiched between (1-ϵ) D and D (where the origin is taken to be the scaled identity matrix) must have linear programming extension complexity at least exp(c sqrt(n)) where c>0 is a constant that depends only on ϵ. The main ingredient of our proof is hypercontractivity of the noise operator on the hypercube.
joint work with Rujun Jiang, Peng Wang, Anthony Man-Cho So
Large-scale quadratically constrained quadratic programming (QCQP) finds many applications in signal processing. Traditional methods, like semidefinite relaxation (SDR) and successive convex approximation (SCA), become inefficient because they are sensitive to the problem dimension. Thus, we are motivated to design a fast fisrt-order method, called linear programming-assisted subgradient decent (LPA-SD), to tackle it. For LPA-SD, we only solve a dimension-free linear programming in each iterate. Numerical results demonstrate its potential in both computational efficiency and solution quality.
joint work with Sherry Ni, K-F Cheung
Source localization is among the most fundamental and studied problems in signal processing. In this talk, we consider the problem of localizing multiple sources based on noisy distance measurements between the sources and the sensors, in which the source-measurement association is unknown. We develop a mixed-integer conic relaxation of the problem and propose a second-order cone-based outer approximation algorithm for solving it. We show that the proposed algorithm enjoys finite convergence and present numerical results to demonstrate its viability.