Subsampling Algorithms for Semidefinite Programming

References

• Achlioptas, D. and McSherry, F. (2007). Fast computation of low-rank matrix approximations. Journal of the ACM 54. MR2295993Google Scholar
• Alon, A., Barkai, N., Notterman, D. A., Gish, K., Ybarra, S., Mack, D. and Levine, A. J. (1999). Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Cell Biology 96 6745–6750.Google Scholar
• Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A.et al.. (1999). LAPACK Users’ guide. Society for Industrial Mathematics.Google Scholar
• Arora, S. and Kale, S. (2007). A combinatorial, primal-dual approach to semidefinite programs In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing 227–236. MR2402446Google Scholar
• Bach, F. (2007). Consistency of trace norm minimization. To appear in Journal of Machine Learning Research. Arxiv preprint arXiv:0710.2848. MR2417263Google Scholar
• Burke, J., Lewis, A. and Overton, M. (2002). Approximating Subdifferentials by Random Sampling of Gradients. Mathematics of Operations Research 27 567–584. MR1926659Link, Google Scholar
• Burke, J. V., Lewis, A. S. and Overton, M. L. (2005). A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization. SIAM Journal on Optimization 15 751–779. MR2142859Google Scholar
• Candes, E. J. and Recht, B. (2008). Exact matrix completion via convex optimization. preprint. MR2565240Google Scholar
• d’Aspremont, A., Banerjee, O. and El Ghaoui, L. (2006). First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Applications 30 56–66. MR2399568Google Scholar
• d’Aspremont, A., El Ghaoui, L., Jordan, M. I. and Lanckriet, G. R. G. (2007). A Direct Formulation for Sparse PCA Using Semidefinite Programming. SIAM Review 49 434–448. MR2353806Google Scholar
• Dhillon, I. S. and Parlett, B. N. (2003). Orthogonal Eigenvectors and Relative Gaps. SIAM Journal on Matrix Analysis and Applications 25 858–899. MR2081239Google Scholar
• Dhillon, I. S., Parlett, B. N. and Vömel, C. (2006). The design and implementation of the MRRR algorithm. ACM Transactions on Mathematical Software (TOMS) 32 560. MR2290445Google Scholar
• Diaconis, P. (2003). Patterns in Eigenvalues: The 70th Josiah Willard Gibbs Lecture. Bulletin of the American Mathematical Society 40 155–178. MR1962294Google Scholar
• Drineas, P., Kannan, R. and Mahoney, M. W. (2006). Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM Journal on Computing 36 158. MR2231644Google Scholar
• Drineas, P., Kannan, R. and Mahoney, M. W. (2007). Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing 36 132–157. MR2231643Google Scholar
• El Karoui, N. (2007). Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices. Annals of Probability 35 663–714. MR2308592Google Scholar
• Fazel, M., Hindi, H. and Boyd, S. (2001). A rank minimization heuristic with application to minimum order system approximation. Proceedings American Control Conference 6 4734–4739.Google Scholar
• Frieze, A., Kannan, R. and Vempala, S. (2004). Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM) 51 1025–1041. MR2145262Google Scholar
• Goemans, M. X. and Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42 1115–1145. MR1412228Google Scholar
• Golub, G. H. and Van Loan, C. F. (1990). Matrix Computation. North Oxford Academic.Google Scholar
• Horn, R. A. and Johnson, C. R. (1991). Topics in matrix analysis. Cambridge university press. MR1091716Google Scholar
• Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Annals of Statistics 295–327. MR1863961Google Scholar
• Juditsky, A., Nemirovskii, A. S. and Tauvel, C. (2008). Solving variational inequalities with Stochastic Mirror-Prox algorithm. Arxiv preprint arXiv:0809.0815.Google Scholar
• Juditsky, A., Lan, G., Nemirovski, A. and Shapiro, A. (2009). Stochastic Approximation Approach to Stochastic Programming. SIAM Journal on Optimization 19 1574–1609. MR2486041Google Scholar
• Kannan, R. and Vempala, S. (2009). Spectral algorithms. MR2558901Google Scholar
• Kuczynski, J. and Wozniakowski, H. (1992). Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl 13 1094–1122. MR1182715Google Scholar
• Kumar, K., Bhattacharya, C. and Hariharan, R. (2008). A Randomized Algorithm for Large Scale Support Vector Learning. In Advances in Neural Information Processing Systems 20 (J. C. Platt, D. Koller, Y. Singer and S. Roweis, eds.) MIT Press, Cambridge, MA.Google Scholar
• Lan, G. (2009). An optimal method for stochastic composite optimization. Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, 2009.Google Scholar
• Lanckriet, G. R. G., Cristianini, N., Bartlett, P., El Ghaoui, L. and Jordan, M. I. (2002). Learning the Kernel Matrix with Semi-Definite Programming. 19th International Conference on Machine Learning.Google Scholar
• Lehoucq, R. B., Sorensen, D. C. and Yang, C. (1998). ARPACK: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. Society for Industrial & Applied Mathematics. MR1621681Google Scholar
• Nemirovsky, A. and Yudin, D. (1983). Problem complexity and method efficiency in optimization. MR0702836Google Scholar
• Nesterov, Y. (2007). Gradient methods for minimizing composite objective function. CORE DP2007/96.Google Scholar
• Nesterov, Y. (2009). Primal-dual subgradient methods for convex problems. Mathematical programming Series B 120 221–259. MR2496434Google Scholar
• Parlett, B., Simon, H. and Stringer, L. (1982). On estimating the largest eigenvalue with the Lanczos algorithm. Mathematics of Computation 38 153–165. MR0637293Google Scholar
• Polyak, B. and Juditsky, A. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30 838. MR1167814Google Scholar
• Polyak, B. T. and Shcherbakov, P. S. (2007). A RANDOMIZED METHOD FOR SOLVING SEMIDEFINITE PROGRAMS. 9th IFAC Workshop on Adaptation and Learning in Control and Signal Processing.Google Scholar
• Recht, B., Fazel, M. and Parrilo, P. A. (2007). Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. Arxiv preprint arXiv:0706.4138. MR2680543Google Scholar
• Rudelson, M. and Vershynin, R. (2007). Sampling from large matrices: An approach through geometric functional analysis. J. ACM 54 21. MR2351844Google Scholar
• Saad, Y. (1992). Numerical methods for large eigenvalue problems. Manchester Univ Press. MR1177405Google Scholar
• Srebro, N. (2004). Learning with Matrix Factorization PhD thesis, Massachusetts Institute of Technology. MR2717223Google Scholar
• Stewart, G. W. (2001). Matrix Algorithms Vol. II: Eigensystems. Society for Industrial Mathematics. MR1853468Google Scholar
• Stewart, G. W. and Sun, J. (1990). Matrix perturbation theory. MR1061154Google Scholar
• Sun, J., Boyd, S., Xiao, L. and Diaconis, P. (2006). The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Review 48 681. MR2278445Google Scholar
• Van der Sluis, A. and Van der Vorst, H. (1987). The convergence behavior of Ritz values in the presence of close eigenvalues. Linear Algebra and its Applications 88 651–694. MR0882466Google Scholar
• Weinberger, K. Q. and Saul, L. K. (2006). Unsupervised Learning of Image Manifolds by Semidefinite Programming. International Journal of Computer Vision 70 77–90.Google Scholar