Row products of random matrices

DOI10.1016/J.AIM.2012.08.010MaRDI QIDQ1759375zbMATH OpenOpenAlexFDO

Authors Mark Rudelson

Publication date 20 November 2012

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extreme singular valuesprivacy protectionrandom matrices

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: We define the row product of K matrices of size d by n as a matrix of size d^K by n, whose row are entry-wise products of rows of these matrices. This construction arises in certain computer science problems. We study the question, to which extent the spectral and geometric properties of the row product of independent random matrices resemble those properties for a d^K by n matrix with independent random entries. In particular, we show that the largest and the smallest singular values of these matrices are of the same order, as long as n is significantly smaller than d^K. We also consider a problem of privately releasing the summary information about a database, and use the previous results to obtain a bound for the minimal amount of noise, which has to be added to the released data to avoid a privacy breach.

Review text

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.

Recommendations

• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Spectral norm of products of random and deterministic matrices
• Random matrix products: universality and least singular values
• On the singular values of random matrices
• On singular values of matrices with independent rows

Cites work

• A limit theorem for the norm of random matrices
• A new look at independence
• Combinatorial Algorithms for Compressed Sensing
• Euclidean embeddings in spaces of finite volume ratio via random matrices
• How close is the sample covariance matrix to the actual covariance matrix?
• scientific article; zbMATH DE number 5485456 (Why is no real title available?)
• scientific article; zbMATH DE number 3944477 (Why is no real title available?)
• scientific article; zbMATH DE number 3672934 (Why is no real title available?)
• scientific article; zbMATH DE number 194093 (Why is no real title available?)
• scientific article; zbMATH DE number 3551404 (Why is no real title available?)
• scientific article; zbMATH DE number 3613664 (Why is no real title available?)
• Lower estimates for the singular values of random matrices
• On sparse reconstruction from Fourier and Gaussian measurements
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Stochastic combinational networks
• The concentration of measure phenomenon
• The Generic Chaining
• The Littlewood-Offord problem and invertibility of random matrices
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Weak convergence and empirical processes. With applications to statistics

Cited in

(9)

• Concentration inequalities for random tensors
• scientific article; zbMATH DE number 3842887 (Why is no real title available?)
• Fingerprinting codes and the price of approximate differential privacy
• Products of Random Rectangular Matrices
• Low-rank Tucker approximation of a tensor from streaming data
• On the hereditary discrepancy of homogeneous arithmetic progressions
• Randomized numerical linear algebra: Foundations and algorithms
• ``Random random matrix products
• Extremal eigenvalues of random kernel matrices with polynomial scaling

This page was built for publication: Row products of random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759375)