Finding Approximately Rank-One Submatrices with the Nuclear Norm and $\ell_1$-Norm

DOI10.1137/100814251zbMath1297.90114arXiv1011.1839OpenAlexW2028126706MaRDI QIDQ5408229

Xuan Vinh Doan, Stephen A. Vavasis

Publication date: 9 April 2014

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1839

zbMATH Keywords

nuclear normnonnegative matrix factorizationrandom noiserank-one submatrixsubmatrix recoverability

Mathematics Subject Classification ID

Factorization of matrices (15A23) Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Random matrices (algebraic aspects) (15B52)

Related Items

Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Sparse and low-rank matrix regularization for learning time-varying Markov networks, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Extreme point inequalities and geometry of the rank sparsity ball, Max-norm optimization for robust matrix recovery, Finding the Largest Low-Rank Clusters With Ky Fan $2$-$k$-Norm and $\ell_1$-Norm, Lower bounds on nonnegative rank via nonnegative nuclear norms, On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation, On certain optimization problems related to matrix norms