全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2013 

Conditions for Existence of Dual Certificates in Rank-One Semidefinite Problems

DOI: 10.4310/CMS.2014.v12.n7.a11

Full-Text   Cite this paper   Add to My Lib

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-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133