Approximating sparse binary matrices in the cut-norm

作者：Alon Noga^*

来源：Linear Algebra and Its Applications, 2015, 486: 409-418.

DOI：10.1016/j.laa.2015.08.024

• Cutnorm
• Low rank approximation

The cut-norm parallel to A parallel to(C) of a real matrix A = (a(ij))(i is an element of R,j is an element of S) is the maximum, over all I subset of R, J subset of S of the quantity vertical bar Sigma(i is an element of I,j is an element of J) a(ij)vertical bar. We show that there is an absolute positive constant c so that if A is the n by n identity matrix and B is a real n by n matrix satisfying p

• 出版日期2015-12-1