Nuclear norm minimization for the planted clique and biclique problems
From MaRDI portal
Publication:717132
DOI10.1007/s10107-011-0459-xzbMath1271.90056arXiv0901.3348OpenAlexW2116616571MaRDI QIDQ717132
Brendan P. W. Ames, Stephen A. Vavasis
Publication date: 27 September 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0901.3348
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Convex programming (90C25)
Related Items
Tensor clustering with planted structures: statistical optimality and computational limits, Multiple phase tabu search for bipartite Boolean quadratic programming with partitioned variables, The Bipartite QUBO, \(s\)-goodness for low-rank matrix recovery, Optimal detection of sparse principal components in high dimension, A simple spectral algorithm for recovering planted partitions, A divide-and-conquer algorithm for binary matrix completion, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, An approximation theory of matrix rank minimization and its application to quadratic equations, Clustering heterogeneous financial networks, Null space conditions and thresholds for rank minimization, An implementable proximal point algorithmic framework for nuclear norm minimization, Convex optimization for the planted \(k\)-disjoint-clique problem, Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation, Guaranteed clustering and biclustering via semidefinite programming, A new approximation of the matrix rank function and its application to matrix rank minimization, Extreme point inequalities and geometry of the rank sparsity ball, A partial proximal point algorithm for nuclear norm regularized matrix least squares problems, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Finding a low-rank basis in a matrix subspace, Computational and statistical tradeoffs via convex relaxation, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time, Primal-Dual Interior-Point Methods for Domain-Driven Formulations, Euclidean Distance Matrices and Applications, Convex optimization for the densest subgraph and densest submatrix problems, Community detection in sparse networks via Grothendieck's inequality, On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation, Exact Clustering of Weighted Graphs via Semidefinite Programming, On solving the densestk-subgraph problem on large graphs, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Computational barriers in minimax submatrix detection, Do semidefinite relaxations solve sparse PCA up to the information limit?
Cites Work
- Unnamed Item
- Unnamed Item
- A limit theorem for the norm of random matrices
- The eigenvalues of random symmetric matrices
- Characterization of the subdifferential of some matrix norms
- The maximum edge biclique problem is NP-complete
- Exact matrix completion via convex optimization
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Near-optimal sparse fourier representations via sampling
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Finding and certifying a large hidden clique in a semirandom graph
- Probability Inequalities for Sums of Bounded Random Variables
- Probability and Computing
- Compressed sensing
- Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures
