Conditions for existence of dual certificates in rank-one semidefinite problems

DOI10.4310/CMS.2014.V12.N7.A11zbMATH Open1335.90065arXiv1303.1598OpenAlexW1982916027MaRDI QIDQ484743FDOQ484743

Authors: Paul E. Hand 

Publication date: 7 January 2015

Published in: Communications in Mathematical Sciences (Search for Journal in Brave)

Abstract: Several signal recovery tasks can be relaxed into semidefinite programs with rank-one minimizers. A common technique for proving these programs succeed is to construct a dual certificate. Unfortunately, dual certificates may not exist under some formulations of semidefinite programs. In order to put problems into a form where dual certificate arguments are possible, it is important to develop conditions under which the certificates exist. In this paper, we provide an example where dual certificates do not exist. We then present a completeness condition under which they are guaranteed to exist. For programs that do not satisfy the completeness condition, we present a completion process which produces an equivalent program that does satisfy the condition. The important message of this paper is that dual certificates may not exist for semidefinite programs that involve orthogonal measurements with respect to positive-semidefinite matrices. Such measurements can interact with the positive-semidefinite constraint in a way that implies additional linear measurements. If these additional measurements are not included in the problem formulation, then dual certificates may fail to exist. As an illustration, we present a semidefinite relaxation for the task of finding the sparsest element in a subspace. One formulation of this program does not admit dual certificates. The completion process produces an equivalent formulation which does admit dual certificates.

Full work available at URL: https://arxiv.org/abs/1303.1598

Recommendations

• On the simplicity and conditioning of low rank semidefinite programs
• Duality formulations in semidefinite programming
• A class of semidefinite programs with rank-one solutions
• Semidefinite programming for discrete optimization and matrix completion problems
• \(s\)-semigoodness for low-rank semidefinite matrix recovery

zbMATH Keywords

convex optimizationliftingstrong dualitysemidefinite relaxationsignal recoverydual certificates

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Semidefinite programming (90C22) Duality theory (optimization) (49N15)

Cited In (1)

• Reconstruction of signals from magnitudes of redundant representations: the complex case

This page was built for publication: Conditions for existence of dual certificates in rank-one semidefinite problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484743)