Row products of random matrices

DOI10.1016/J.AIM.2012.08.010zbMATH Open1258.15017arXiv1102.1947OpenAlexW1963520997MaRDI QIDQ1759375FDOQ1759375

Authors: Mark Rudelson 

Publication date: 20 November 2012

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

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.

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

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

zbMATH Keywords

privacy protectionrandom matricesextreme singular values

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Randomized numerical linear algebra: Foundations and algorithms
• Title not available (Why is that?)
• ``Random random matrix products
• Fingerprinting codes and the price of approximate differential privacy
• On the hereditary discrepancy of homogeneous arithmetic progressions
• Low-rank Tucker approximation of a tensor from streaming data
• Concentration inequalities for random tensors
• Products of Random Rectangular Matrices

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)