Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis

References

• [1] Ajtai M, Komlós J, Szemerédi E (1983) An O(nlog n) sorting network. Proc. 15th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 1–9.Google Scholar
• [2] Argyriou A, Foygel R, Srebro N (2012) Sparse prediction with the k-support norm. Pereira F, Burges CJC, Bottou L, Weinberger KQ, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 25:1457–1465.Google Scholar
• [3] Balas E (2018) Disjunctive Programming (Springer, Cham, Switzerland).Crossref, Google Scholar
• [4] Barvinok AI (2002) A Course in Convexity (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [5] Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 (SIAM, Philadelphia).Crossref, Google Scholar
• [6] Bertsimas D, Cory-Wright R, Pauphilet J (2020) Solving large-scale sparse PCA to certifiable (near) optimality. Preprint, submitted May 11, https://arxiv.org/abs/2005.05195.Google Scholar
• [7] d’Aspremont A, El Ghaoui L, Jordan MI, Lanckriet GR (2007) A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3):434–448.Crossref, Google Scholar
• [8] Fiorini S, Massar S, Pokutta S, Tiwary HR, de Wolf R (2015) Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2):17.Crossref, Google Scholar
• [9] Goemans MX (2015) Smallest compact formulation for the permutahedron. Math. Programming 153(1):5–11.Crossref, Google Scholar
• [10] Grant M, Boyd S (2008) Graph implementations for nonsmooth convex programs. Blondel V, Boyd S, Kimura H, eds. Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences, vol. 371 (Springer-Verlag, London), 95–110.Crossref, Google Scholar
• [11] Grant M, Boyd S (2014) CVX: Matlab software for disciplined convex programming. V. 2.1. http://cvxr.com/cvx.Google Scholar
• [12] Hardy G, Littlewood J, Pólya G (1952) Inequalities (Cambridge University Press, Cambridge, UK).Google Scholar
• [13] Hiriart-Urruty JB, Le HY (2012) Convexifying the set of matrices of bounded rank: Applications to the quasiconvexification and convexification of the rank function. Optim. Lett. 6(5):841–849.Crossref, Google Scholar
• [14] Horn RA, Johnson CR (2012) Matrix Analysis, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [15] Jeffers J (1967) Two case studies in the application of principal component analysis. J. Royal Statist. Soc. Ser. C. Appl. Statist. 16(3):225–236.Google Scholar
• [16] Kaibel V, Pashkovich K (2011) Constructing extended formulations from reflection relations. Günlük O, Woeginger GJ, eds. Proc. 15th Internat. Conf. Integer Programming Combin. Optim. Lecture Notes in Computer Science, vol. 6655 (Springer, Berlin), 287–300.Google Scholar
• [17] Kim J, Tawarmalani M, Richard JPP (2019) Convexification of permutation-invariant sets and applications. Preprint, submitted October 7, https://arxiv.org/abs/1910.02573.Google Scholar
• [18] Lewis AS (1995) The convex analysis of unitarily invariant matrix functions. J. Convex Anal. 2(1):173–183.Google Scholar
• [19] Li CK, Mehta PP (1995) Permutation invariant norms. Linear Algebra Appl. 219:93–110.Crossref, Google Scholar
• [20] Lim CH (2017) A note on extended formulations for cardinality-based sparsity. Proc. 10th Neural Inform. Processing Systems Workshop Optim. Machine Learn. (Long Beach, CA).Google Scholar
• [21] Lim CH, Wright S (2017) k-support and ordered weighted sparsity for overlapping groups: Hardness and algorithms. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 284–292.Google Scholar
• [22] Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Hara S, Fu LC, Ge SS, Samad T, Sebek M, Engell S, eds. Proc. IEEE Internat. Sympos. Comput. Aided Control System Design (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 284–289.Google Scholar
• [23] Luedtke J, Namazifar M, Linderoth J (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136(2):325–351.Crossref, Google Scholar
• [24] Marshall AW, Olkin I, Arnold B (2010) Inequalities: Theory of Majorization and Its Applications (Springer-Verlag, New York).Google Scholar
• [25] Matoušek J (2002) Lectures on Discrete Geometry, vol. 212 (Springer-Verlag, New York).Crossref, Google Scholar
• [26] MOSEK ApS (2017) MOSEK optimization suite. Accessed June 11, 2021, https://www.mosek.com/.Google Scholar
• [27] Nemirovski A (2012) Introduction to linear optimization, ISYE 6661. Lecture notes, Georgia Institute of Technology, Atlanta.Google Scholar
• [28] Nguyen TT, Richard JPP, Tawarmalani M (2018) Deriving convex hulls through lifting and projection. Math. Programming 169(2):377–415.Crossref, Google Scholar
• [29] Rado R (1952) An inequality. J. London Math. Soc. 27(1):1–6.Crossref, Google Scholar
• [30] Rikun AD (1997) A convex envelope formula for multilinear functions. J. Global Optim. 10(4):425–437.Crossref, Google Scholar
• [31] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ), 284–289.Crossref, Google Scholar
• [32] Tawarmalani M, Richard JPP (2017) Decomposition techniques in convexification of sets. Working paper, Krannert School of Management, Purdue University, West Lafayette, IN.Google Scholar
• [33] Tillmann AM, Pfetsch ME (2013) The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inform. Theory 60(2):1248–1259.Crossref, Google Scholar
• [34] Zou H, Hastie T, Tibshirani R (2006) Sparse principal component analysis. J. Comput. Graphical Statist. 15(2):265–286.Crossref, Google Scholar