TY - GEN
T1 - Sparse approximate solutions to semidefinite programs
AU - Hazan, Elad
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=43049120013&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=43049120013&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-78773-0_27
DO - 10.1007/978-3-540-78773-0_27
M3 - Conference contribution
AN - SCOPUS:43049120013
SN - 3540787720
SN - 9783540787723
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 306
EP - 316
BT - LATIN 2008
T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008
Y2 - 7 April 2008 through 11 April 2008
ER -