Row products of random matrices (Q1759375)

The spectral and geometric properties of a certain class of random matrices with dependent rows created from random matrices with independent entries are studied. For two matrices with the same number of rows the so-called row product is defined as a matrix whose rows consist of the entry-wise product of the rows of original matrices. Generally, the row product of several matrices \(\Delta_1, \dots, \Delta_K\) with dimensions \(d \times n\) is defined as a \(d^K \times n\) matrix with rows which are entry-wise products of rows of \(\Delta_1, \dots, \Delta_K\) matrices. Such constructions first appeared in computer science in the study of privacy protection. In the paper, it is proved that the extreme singular values of the row product of several random matrices behave like the singular values of the matrices \(d^K \times n\) with independent entries. Especially, it is shown that as \(n << d^K\) the largest and the smallest singular values are of the same order for these matrices. An estimation on the minimal amount of noise needed to avoid a privacy breach in privacy protection problem [\textit{S.~P. Kasiviswanathan, M. Rudelson, A. Smith} and \textit{J. Ullman}, STOC, 775--784 (2010)] is derived.