We propose a convex optimization formulation using nuclear norm and l1-norm to find a large low-rank submatrix for a given matrix. We are able to characterize the low-rank and sparsity structure of the resulting solutions. We show that our model can recover low-rank submatrices for matrices with subgaussian random noises. We solve the proposed model using a proximal point algorithm and apply it to an application in image feature extraction.

Joint work with X. V. Doan of Waterloo and Warwick