Structured Semi-Definite Programming with Applications to Non-Gaussian Component Analysis

Yury Maximov (IITP RAS, Moscow)
Wednesday, May 25, 2016 - 10:00am
WIAS, Erhard-Schmidt-Saal, Mohrenstraße 39, 10117 Berlin

Semi-definite programming (SDP) is a popular tool for approximation of non-convex quadratic problems arises in multiple statistical and computer science problems. Known to be worst-case optimal SDP is often dominated on well-structured (practical) problems by domain specific methods and heuristics. Yet another problem of SDP is a slow computational time makes it hardly applicable for huge-scale problems. In this talk we try to incorporate problem structure in the semi-definite dual to contribute both decrease computational time and improve approximation guarantees. A major application the proposed structured semi-definite programming is a novel convex projection based method in Non-gaussian component analysis (NGCA) especially efficient for projecting sparse and low-rank high-dimensional data. The talk is based on the joint research results with Yu. Nesterov (CORE/UCL, Belgium) and V. Spokoiny (WIAS, Berlin)