Sparse approximate solutions to semidefinite programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

88 Scopus citations


We propose an algorithm for approximately maximizing a concave function over the bounded semi-definite cone, which produces sparse solutions. Sparsity for SDP corresponds to low rank matrices, and is a important property for both computational as well as learning theoretic reasons. As an application, building on Aaronson's recent work, we derive a linear time algorithm for Quantum State Tomography.

Original languageEnglish (US)
Title of host publicationLATIN 2008
Subtitle of host publicationTheoretical Informatics - 8th Latin American Symposium, Proceedings
Number of pages11
StatePublished - 2008
Externally publishedYes
Event8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil
Duration: Apr 7 2008Apr 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4957 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th Latin American TheoreticalINformatics Symposium, LATIN 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Sparse approximate solutions to semidefinite programs'. Together they form a unique fingerprint.

Cite this