Optimal detection of sparse principal components in high dimension
The Annals of StatisticsPublished 1 August 2013Open access
Quentin Berthet, Philippe Rigollet
Citations263
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The minimax optimal test is based on a sparse eigenvalue statistic, and a computationally efficient alternative test using convex relaxations is described, which is proved to detect sparse principal components at near optimal detection levels and performs well on simulated datasets.
Abstract
We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels, and it performs well on simulated datasets. Moreover, using polynomial time reductions from theoretical computer science, we bring significant evidence that our results cannot be improved, thus revealing an inherent trade off between statistical and computational performance.
Keywords
MathematicsEngineering
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
Society for Industrial and Applied Mathematics eBooksInterior-Point Polynomial Algorithms in Convex Programming
4,275 Citations1994Yurii Nesterov, Arkadi Nemirovski
This book describes the first unified theory of polynomial-time interior-point methods, and describes several of the new algorithms described, e.g., the projective method, which have been implemented, tested on "real world" problems, and found to be extremely efficient in practice.
Proceedings of the National Academy of SciencesBroad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays
4,210 Citations1999Uri Alon, Naama Barkai +5 more
A two-way clustering method is reported for analyzing a data set consisting of the expression patterns of different cell types, revealing broad coherent patterns that suggest a high degree of organization underlying gene expression in these tissues.
Journal of the ACMImproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
3,684 Citations1995Michel X. Goemans, David P. Williamson
This algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of semidefinite programming in the design of approximation algorithms.
ACM SIGACT NewsIntroduction to the Theory of Computation
2,792 Citations1996Michael Sipser
Throughout the book, Sipser builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own.
Springer series in statisticsIntroduction to Nonparametric Estimation
2,523 Citations2008Alexandre B. Tsybakov
The main idea is to introduce the fundamental concepts of the theory while maintaining the exposition suitable for a first approach in the field, and many important and useful results on optimal and adaptive estimation are provided.
The Annals of StatisticsOn the distribution of the largest eigenvalue in principal components analysis
2,042 Citations2001Iain M. Johnstone
Reducibility Among Combinatorial Problems
1,368 Citations2012Kichard Rarp
Covariance regularization by thresholding
1,171 Citations2007Peter J. Bickel, Elizaveta Levina
The Annals of StatisticsAdaptive estimation of a quadratic functional by model selection
1,083 Citations2000Béatrice Laurent, Pascal Massart
A general nonasymptotic risk bound is proved which allows us to show that such penalized estimators are adaptive on a variety of collections of sets for the parameter s, depending on the family of models from which they are built.
The Annals of ProbabilityPhase transition of the largest eigenvalue for nonnull complex sample covariance matrices
944 Citations2005Jinho Baik, Gérard Ben Arous +1 more
Journal of the American Statistical AssociationOn Consistency and Sparsity for Principal Components Analysis in High Dimensions
864 Citations2009Iain M. Johnstone, Arthur Yu Lu
A simple algorithm for selecting a subset of coordinates with largest sample variances is provided, and it is shown that if PCA is done on the selected subset, then consistency is recovered, even if p(n) ≫ n.
The Annals of StatisticsCovariance regularization by thresholding
862 Citations2008Peter J. Bickel, Elizaveta Levina
It is shown that the thresholded estimate is consistent in the operator norm as long as the true covariance matrix is sparse in a suitable sense, the variables are Gaussian or sub-Gaussian, and $(\log p)/n\to0$, and obtain explicit rates.
The Annals of StatisticsHigher criticism for detecting sparse heterogeneous mixtures
762 Citations2004David L. Donoho, Jiashun Jin
Journal of Multivariate AnalysisEigenvalues of large sample covariance matrices of spiked population models
735 Citations2005Jinho Baik, Jack W. Silverstein
SIAM ReviewA Direct Formulation for Sparse PCA Using Semidefinite Programming
667 Citations2007Alexandre d’Aspremont, Laurent El Ghaoui +2 more
ASYMPTOTICS OF SAMPLE EIGENSTRUCTURE FOR A LARGE DIMENSIONAL SPIKED COVARIANCE MODEL
647 Citations2007Debashis Paul
The Annals of StatisticsHigh-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
555 Citations2012Po‐Ling Loh, Martin J. Wainwright
This work is able to both analyze the statistical error associated with any global optimum, and prove that a simple algorithm based on projected gradient descent will converge in polynomial time to a small neighborhood of the set of all global minimizers.
arXiv (Cornell University)Generalized power method for sparse principal component analysis
500 Citations2008Michel Journée, Yurii Nesterov +2 more
The Annals of ProbabilityA Limit Theorem for the Norm of Random Matrices
442 Citations1980Stuart Geman
Operator norm consistent estimation of large-dimensional sparse covariance matrices
366 Citations2012Noureddine El Karoui
Society for Industrial and Applied Mathematics eBooksTen Lectures on the Probabilistic Method
360 Citations1994Joel Spencer
Probability Theory and Related FieldsOn the limit of the largest eigenvalue of the large dimensional sample covariance matrix
354 Citations1988Yanqing Yin, Zhidong Bai +1 more
The Annals of StatisticsSparse principal component analysis and iterative thresholding
329 Citations2013Zongming Ma
Under a spiked covariance model, a new iterative thresholding approach for estimating principal subspaces in the setting where the leading eigenvectors are sparse is proposed and it is found that the new approach recovers the principal subspace and leading eignevectors consistently, and even optimally, in a range of high-dimensional sparse settings.
Random Structures and AlgorithmsLarge Cliques Elude the Metropolis Process
326 Citations1992Mark Jerrum
It is shown that the Metropolis process takes super-polynomial time to locate a clique that is only slightly bigger than that produced by the greedy heuristic, which is one step above the greedy one in its level of sophistication.
The Annals of StatisticsOptimal rates of convergence for covariance matrix estimation
301 Citations2010T. Tony Cai, Cun-Hui Zhang +1 more
ArXiv.orgStructured Sparse Principal Component Analysis
295 Citations2009Rodolphe Jenatton, Guillaume Obozinski +1 more
The Annals of StatisticsSparse PCA: Optimal rates and adaptive estimation
289 Citations2013Tommaso Cai, Zongming Ma +1 more
Under mild technical conditions, this paper establishes the optimal rates of convergence for estimating the principal subspace which are sharp with respect to all the parameters, thus providing a complete characterization of the difficulty of the estimation problem in term of the convergence rate.
The Annals of StatisticsSpectrum estimation for large dimensional covariance matrices using random matrix theory
275 Citations2008Noureddine El Karoui
This work proposes to use a fundamental result in random matrix theory, the Marcenko-Pastur equation, to better estimate the eigenvalues of large dimensional covariance matrices, and suggests a change of point of view when thinking about estimation of high-dimensional vectors: it does not try to estimate directly the vectors but rather a probability measure that describes them.
Random Structures and AlgorithmsFinding a large hidden clique in a random graph
265 Citations1998Noga Alon, Michael Krivelevich +1 more
This paper presents an efficient algorithm for finding a hidden clique of vertices of size k that is based on the spectral properties of the graph and improves the trivial case k ) cn log n .
Journal of Machine Learning ResearchOptimal Solutions for Sparse Principal Component Analysis
258 Citations2008Alexandre d’Aspremont, Francis Bach +1 more
The Annals of StatisticsOperator norm consistent estimation of large-dimensional sparse covariance matrices
244 Citations2008Noureddine El Karoui
The estimator is shown to be consistent in operator norm, when, for instance, the authors have p ?
The Annals of StatisticsFinite sample approximation results for principal component analysis: A matrix perturbation approach
206 Citations2008Boaz Nadler
A matrix perturbation view of the "phase transition phenomenon," and a simple linear-algebra based derivation of the eigenvalue and eigenvector overlap in this asymptotic limit of finite sample PCA are presented.
The Annals of StatisticsGlobal testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
203 Citations2011Ery Arias-Castro, Emmanuel J. Candès +1 more
Random Structures and AlgorithmsFinding and certifying a large hidden clique in a semirandom graph
200 Citations2000Uriel Feige, Robert Krauthgamer
This work shows that a different algorithm, based on the Lovasz theta function, almost surely both finds the hidden clique and certifies its optimality and has an additional advantage of being more robust: it also works in a semirandomhidden clique model, in which an adversary can remove edges from the random portion of the graph.
Journal of Machine Learning ResearchGeneralized Power Method for Sparse Principal Component Analysis
199 Citations2010JournéeMichel, NesterovYurii +2 more
A new approach to sparse principal component analysis (sparse PCA) aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively is developed.
Discrete Applied MathematicsExpected complexity of graph partitioning problems
197 Citations1995Luděk Kučera
The expected time complexity of two graph partitioning problems: the graph coloring and the cut into equal parts is studied to obtain a sublinear expected time algorithm for k-coloring of k-colorable graphs.
Proceedings of the National Academy of SciencesComputational and statistical tradeoffs via convex relaxation
192 Citations2013Venkat Chandrasekaran, Michael I. Jordan
This paper defines a notion of “algorithmic weakening,” in which a hierarchy of algorithms is ordered by both computational efficiency and statistical efficiency, allowing the growing strength of the data at scale to be traded off against the need for sophisticated processing.
The Annals of StatisticsDetection of an anomalous cluster in a network
187 Citations2010Ery Arias-Castro, Emmanuel J. Candès +1 more
This work considers the problem of detecting whether or not in a given sensor network, there is a cluster of sensors which exhibit an "unusual behavior", and considers classes of clusters that are quite general, for which a lower bound is obtained on their respective minimax detection rate.
The Annals of StatisticsMinimax bounds for sparse PCA with noisy high-dimensional data
183 Citations2013Aharon Birnbaum, Iain M. Johnstone +2 more
A lower bound on the minimax risk of estimators under the l2 loss is established, in the joint limit as dimension and sample size increase to infinity, under various models of sparsity for the population eigenvectors.
IEEE Transactions on Information TheoryCertifying the Restricted Isometry Property is Hard
164 Citations2013Afonso S. Bandeira, Edgar Dobriban +2 more
It is demonstrated that testing whether a matrix satisfies RIP is NP-hard, which means it is impossible to efficiently test for RIP provided P ≠ NP.
Open Repository and Bibliography (University of Luxembourg)Non-asymptotic minimax rates of testing in signal detection
147 Citations2002Yannick Baraud
The minimal `2-distance between f and 0 is described for the problem of testing “ f = 0” against “f 6= 0, f ∈ F” to be possible with prescribed probabilities of error and to handle the cases where F is an ellipsoid and more generally an `p-body with p ∈]0, 2].
The Annals of StatisticsAsymptotic power of sphericity tests for high-dimensional data
130 Citations2013Alexei Onatski, Marcelo J. Moreira +1 more
Electronic Journal of ProbabilityFluctuations of the Extreme Eigenvalues of Finite Rank Deformations of Random Matrices
122 Citations2011Florent Benaych-Georges, Alice Guionnet +1 more
The Annals of StatisticsHigh-dimensional analysis of semidefinite relaxations for sparse principal components
120 Citations2009Arash A. Amini, Martin J. Wainwright
This paper analyzes a simple and computationally inexpensive diagonal cut-off method, and establishes a threshold of the order thetasdiag = n/[k2 log(p-k)] separating success from failure, and proves that a more complex semidefinite programming (SDP) relaxation due to dpsilaAspremont et al., succeeds once the sample size is of theorder thetassdp.
Mathematical ProgrammingNuclear norm minimization for the planted clique and biclique problems
119 Citations2011Brendan Ames, Stephen A. Vavasis
This work considers the problems of finding a maximum clique in a graph and finding amaximum-edge biclique in a bipartite graph and writes both problems as matrix-rank minimization and then relax them using the nuclear norm.
SIAM Journal on ComputingHow Hard Is It to Approximate the Best Nash Equilibrium?
118 Citations2011Elad Hazan, Robert Krauthgamer
The quest for a PTAS for Nash equilibrium in a two-player game seeks to circumvent the PPAD-completeness of an (exact) Nash equilibrium by finding an approximate equilibrium, and has emerged as a major open question in Algorithmic Game Theory.
BernoulliDetection of a sparse submatrix of a high-dimensional noisy matrix
116 Citations2013Cristina Butucea, Yuri I. Ingster
The authors' sharp minimax results are extended in different directions: first, to Gaussian matrices with unknown variance, next, to matrices of random variables having a distribution from an exponential family (non-Gaussian) and, finally, to a two-sided alternative forMatrices with Gaussian elements.
Finding a large hidden clique in a random graph
116 Citations1998Noga Alon, Michael Krivelevich +1 more
Mathematical ProgrammingAn augmented Lagrangian approach for sparse principal component analysis
110 Citations2011Zhaosong Lu, Yong Zhang
This paper proposes a new formulation for sparse PCA, aiming at finding sparse and nearly uncorrelated PCs with orthogonal loading vectors while explaining as much of the total variance as possible, and develops a novel augmented Lagrangian method for solving a class of nonsmooth constrained optimization problems.
The Annals of StatisticsOn combinatorial testing problems
104 Citations2010Louigi Addario‐Berry, Nicolas Broutin +2 more
Presented on October 15, 2018 from 12:00 p.m.) in the Groseclose Building, Room 402, Georgia Institute of Technology (Georgia Tech).
Journal of Multivariate AnalysisConsistency of sparse PCA in High Dimension, Low Sample Size contexts
103 Citations2012Dan Shen, Haipeng Shen +1 more
This work extends the existing HDLSS asymptotic consistency and strong inconsistency results of conventional PCA in an entirely new direction and finds a large set of sparsity assumptions under which sparse PCA is still consistent even when conventionalPCA is strongly inconsistent.
Testing k-wise and almost k-wise independence
98 Citations2007Noga Alon, Alexandr Andoni +4 more
This work gives evidence that the time complexity of testing (ε,k)-wise independence is likely to be poly(n, 1/ε,1/δ) for k=Θ(log n), since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs.
arXiv (Cornell University)Optimal Solutions for Sparse Principal Component Analysis
90 Citations2007Alexandre d’Aspremont, Francis Bach +1 more
SIAM Journal on ComputingThe Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
88 Citations2003Uriel Feige, Robert Krauthgamer
It follows that for those relaxations known to be efficiently computable, namely, for r=O(1), the value of the relaxation is comparable to the theta function.
Statistical algorithms and a lower bound for detecting planted cliques
82 Citations2013Vitaly Feldman, Elena Grigorescu +3 more
The main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions when the planted clique has size O(n1/2-δ) for any constant δ > 0.
Designs Codes and CryptographyHiding Cliques for Cryptographic Security
82 Citations2000Ari Juels, Marcus Peinado
It is demonstrated how a well studied combinatorial optimization problem may be used as a new cryptographic primitive by “hiding” large cliques in random graphs by exploiting the conjecture that no polynomial-time algorithm exists which finds a clique of size.
arXiv (Cornell University)Minimax Rates of Estimation for Sparse PCA in High Dimensions
79 Citations2012Vincent Q. Vu, Jing Lei
It is proved optimal, non-asymptotic lower and upper bounds on the minimax estimation error for the leading eigenvector when it belongs to an $\ell_q$ ball for $q \in [0,1]$ over a wide class of distributions.
arXiv (Cornell University)Augmented sparse principal component analysis for high dimensional data
70 Citations2012Debashis Paul, Iain M. Johnstone
This work studies the problem of estimating the leading eigenvectors of a high-dimensional population covariance matrix based on independent Gaussian observations and proposes an estimator based on a coordinate selection scheme combined with PCA that achieves the optimal rate of convergence under a sparsity regime.
Discrete Mathematics & Theoretical Computer ScienceFinding hidden cliques in linear time
69 Citations2010Uriel Feige, Dorit Ron
This manuscript presents a new algorithm for finding hidden cliques that has the advantage of being much simpler, running faster (linear time), and experiments show that the leading constant $c$ is smaller than in the spectral approach.
Journal of Mathematical PhysicsThe largest eigenvalues of sample covariance matrices for a spiked population: Diagonal case
52 Citations2009Delphine Féral, Sandrine Péché
DETECTION OF CORRELATIONS
51 Citations2012Ery Arias-Castro
ScholarlyCommons (University of Pennsylvania)High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
51 Citations2011Po‐Ling Loh, Martin J. Wainwright
UNC LibrariesOn the Size and Recovery of Submatrices of Ones in a Random Binary Matrix
49 Citations2021Xing Sun, Andrew B. Nobel
This paper establishes a three-point concentration result, and a related probability bound, for the size of the largest square submatrix of 1s in a square Bernoulli matrix, and extends these results to non-square matrices and submatrices with fixed aspect ratios.
Leibniz-Zentrum für Informatik (Schloss Dagstuhl)A new approach to the planted clique problem
47 Citations2008Alan Frieze, Ravi Kannan
The problem of finding a large planted clique in the random graph is studied and the problem is reduced to that of maximising a three dimensional tensor over the unit ball in n dimensions.
Journal of Combinatorial OptimizationApproximating the Independence Number and the Chromatic Number in Expected Polynomial Time
45 Citations2002Michael Krivelevich, Van H. Vu
An approximation algorithm is presented for the independence number of graphs on n vertices, whose approximation ratio is O((np)1/2/log n) and whose expected running time over the probability space G(n, p) is polynomial.
Journal of the Operations Research Society of ChinaAlternating Direction Method of Multipliers for Sparse Principal Component Analysis
38 Citations2013Shiqian Ma
An alternating direction method based on a variable-splitting technique and an augmented Lagrangian framework for solving this nonsmooth semidefinite programming problem and guarantees that the resulting matrix is a sparse matrix is proposed.
IEEE Transactions on Information TheoryHidden Cliques and the Certification of the Restricted Isometry Property
37 Citations2014Pascal Koiran, Anastasios Zouzias
It is shown in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard.
Average-case complexity of detecting cliques
36 Citations2010Madhu Sudan, Benjamin Rossman
The results show that, in certain models of computation, solving k-CLIQUE in the average case requires Ω( nk/4) resources (moreover, k/4 is tight), and obtain a novel Size Hierarchy Theorem for uniform AC0.
The Annals of StatisticsDetection of correlations
33 Citations2012Ery Arias-Castro, Sébastien Bubeck +1 more
BernoulliOn the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
32 Citations2013Xing Sun, Andrew B. Nobel
This work identifies size thresholds and associated (asymptotic) probability bounds for both large-average and ANOVA-fit submatrices of a Gaussian random matrix.
Combinatorics Probability ComputingFinding Hidden Cliques in Linear Time with High Probability
28 Citations2013Yael Dekel, Ori Gurel-Gurevich +1 more
A new algorithm for finding hidden cliques that both runs in time O(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to ∞ is presented.
Mathematical ProgrammingApproximation bounds for sparse principal component analysis
26 Citations2014Alexandre d’Aspremont, Francis Bach +1 more
arXiv (Cornell University)Sparsity and Robustness in Face Recognition
23 Citations2011John Wright, Arvind Ganesh +3 more
This report has attempted to clarify some frequently encountered questions about this work and particularly, on the validity of using sparse representation techniques for face recognition.
Random Structures and AlgorithmsFinding and certifying a large hidden clique in a semirandom graph
23 Citations2000Uriel Feige, Robert Krauthgamer
Lecture notes in computer scienceA Matrix Hyperbolic Cosine Algorithm and Applications
19 Citations2012Anastasios Zouzias
This paper generalizes Spencer's hyperbolic cosine algorithm to the matrix-valued setting, and gives an elementary connection between spectral sparsification of positive semi-definite matrices and element-wise matrixSparsification, which implies an improved deterministic algorithm for spectral graph sparsify of dense graphs.
Lecture notes in computer scienceRandom Tensors and Planted Cliques
17 Citations2009S. Charles Brubaker, Santosh S. Vempala
It is shown that the 2-norm of the r -parity tensor is at most $f(r)\sqrt{n}\log^{O(r)}n$, answering a question of Frieze and Kannan who proved this for r = 3.
Lecture notes in computer scienceApproximating the Independence Number and the Chromatic Number in Expected Polynomial Time
16 Citations2000Michael Krivelevich, H. Van Vu
Statistical Applications in Genetics and Molecular BiologyAdaptive Elastic-Net Sparse Principal Component Analysis for Pathway Association Testing
15 Citations2011Xi Chen
This work proposes a two-stage analysis strategy to extract latent variables representing activities within each pathway using a dimension reduction approach based on adaptive elasticnet sparse principal component analysis and integrates the latent variables with the regression modeling framework to analyze studies with different types of outcomes such as binary, continuous or survival outcomes.
arXiv (Cornell University)Spectrum estimation for large dimensional covariance matrices using random matrix theory
11 Citations2006Noureddine El Karoui
arXiv (Cornell University)Convex Relaxations for Subset Selection
10 Citations2010Francis Bach, Selin Damla Ahipaşaoğlu +1 more
This work uses convex relaxation techniques to produce lower bounds on the optimal value of subset selection problems and generates good approximate solutions, and explicitly bound the quality of these relaxations by studying the approximation ratio of sparse eigenvalue relaxations.
arXiv (Cornell University)Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
9 Citations2010Florent Benaych-Georges, Alice Guionnet +1 more
arXiv (Cornell University)Consistency of Sparse PCA in High Dimension, Low Sample Size Contexts
7 Citations2011Dan Shen, Haipeng Shen +1 more
DSpace@MIT (Massachusetts Institute of Technology)Average-case complexity of detecting cliques
6 Citations2010Benjamin Rossman, It T +2 more
arXiv (Cornell University)Outliers in the spectrum of iid matrices with bounded rank perturbations
6 Citations2010Terence Tao
Statistical Algorithms and a Lower Bound for Planted Clique
6 Citations2012Vitaly Feldman, Elena Grigorescu +3 more
A framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning is developed, based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation of any given function on a sample drawn randomly from theinput distribution.
UNC LibrariesConsistency of sparse PCA in High Dimension, Low Sample Size contexts
6 Citations2021Dan Shen, Haipeng Shen +1 more
arXiv (Cornell University)Hidden cliques and the certification of the restricted isometry property
5 Citations2012Pascal Koiran, Anastasios Zouzias
arXiv (Cornell University)Alternating Direction Method of Multipliers for Sparse Principal Component Analysis
3 Citations2011Shiqian Ma
UNC LibrariesOn the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
3 Citations2021Xing Sun, Andrew B. Nobel
Theory of Probability and Its ApplicationsOn the Asymptotic Efficiency of Tests for a Simple Hypothesis Against a Composite Alternative
2 Citations1983Yu. I. Ingster
SSRN Electronic JournalA Direct Formulation for Sparse PCA Using Semidefinite Programming
1 Citations2004Alexandre d’Aspremont, Laurent El Ghaoui +2 more
A modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, is used and derived to derive a semidefinite programming based relaxation for the problem.
…