In this paper, we investigate extreme singular values of the analysis matrix of a Gabor frame @math with a random window @math . Columns of such matrices are time and frequency shifts of @math , and @math is the set of time-frequency shift indices. Our aim is to obtain bounds on the singular values of such random time-frequency structured matrices for various choices of the frame set @math , and to investigate their dependence on the structure of @math , as well as on its cardinality. We also compare the results obtained for Gabor frame analysis matrices with the respective results for matrices with independent identically distributed entries.
The following optimal estimate of the smallest singular value of the analysis matrix for a random subgaussian frame with independent entries is due to Rudelson and Vershynin @cite_1 .
@cite_1
2168494960
We prove an optimal estimate of the smallest singular value of a random sub- Gaussian matrix, valid for all dimensions. For an Nn matrix A with inde- pendent and identically distributed sub-Gaussian entries, the smallest singular value of A is at least of the order p Np n � 1 with high probability. A sharp The classical random matrix theory is mostly focused on asymptotic spectral properties of random matrices as their dimensions grow to infinity. At the same time many recent applications from convex geometry to functional analysis to information theory operate with random matrices in fixed dimensions. This survey addresses the non-asymptotic theory of extreme singular values of random matrices with independent entries. We focus on recently developed geometric methods for estimating the hard edge of random matrices (the smallest singular value). Let @math denote a random symmetric @math matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values @math and @math with probability @math each). It is widely conjectured that @math is singular with probability at most @math . On the other hand, the best known upper bound on the singularity probability of @math , due to Vershynin (2011), is @math , for some unspecified small constant @math . This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of @math is at most @math for all sufficiently large @math . The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij. We present deviation inequalities of random operators of the form 1 N ∑N i=1 Xi ⊗ Xi from the average operator E(X ⊗ X), where Xi are independent random vectors distributed as X, which is a random vector in R or in 2. We use these inequalities to estimate the singular values of random matrices with independent rows (without assuming that the entries are independent). This paper provides novel results for the recovery of signals from undersampled measurements based on analysis @math -minimization, when the analysis operator is given by a frame. We both provide so-called uniform and nonuniform recovery guarantees for cosparse (analysis-sparse) signals using Gaussian random measurement matrices. The nonuniform result relies on a recovery condition via tangent cones and the uniform recovery guarantee is based on an analysis version of the null space property. Examining these conditions for Gaussian random matrices leads to precise bounds on the number of measurements required for successful recovery. In the special case of standard sparsity, our result improves a bound due to Rudelson and Vershynin concerning the exact reconstruction of sparse signals from Gaussian measurements with respect to the constant and extends it to stability under passing to approximately sparse signals and to robustness under noise on the measurements. Recently several results appeared that show significant reduction in time for matrix multiplication, singular value decomposition as well as linear ( 2) regression, all based on data dependent random sampling. Our key idea is that low dimensional embeddings can be used to eliminate data dependence and provide more versatile, linear time pass efficient matrix computation. Our main contribution is summarized as follows. --Independent of the recent results of Har-Peled and of Deshpande and Vempala, one of the first -- and to the best of our knowledge the most efficient -- relative error (1 + ) A - A_k _F approximation algorithms for the singular value decomposition of an m ? n matrix A with M non-zero entries that requires 2 passes over the data and runs in time O ( ( M( k + k k) + (n + m)( k + k k)^2 ) 1 ) --The first o(nd^ 2 ) time (1 + ) relative error approximation algorithm for n ? d linear ( ) regression. --A matrix multiplication and norm approximation algorithm that easily applies to implicitly given matrices and can be used as a black box probability boosting tool. Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is, when the singular values of interest are significantly greater than those of a random matrix with size and entries similar to A. Our technique amounts to independently sampling and or quantizing the entries of A, thus speeding up computation by reducing the number of nonzero entries and or the length of their representation. Our analysis is based on observing that the acts of sampling and quantization can be viewed as adding a random matrix N to A, whose entries are independent random variables with zero-mean and bounded variance. Since, with high probability, N has very weak spectral features, we can prove that the effect of sampling and quantization nearly vanishes when a low-rank approximation to A p N is computed. We give high probability bounds on the quality of our approximation both in the Frobenius and the 2-norm. It is shown that for the n × n-Hadamard matrix (or, more generally, a bounded orthogonal matrix) the RIP-property for r-space vectors holds, with row restriction to a set S of size @math This bound represents a slight improvement over (Rudelson and Vershynin, Commun Pure Appl Math 61:1025–1045, 2008) in that the power of the logarithm is decreased by one unit. In the last few years, the asymptotic distribution of the singular values of certain random matrices has emerged as a key tool in the analysis and design of wireless communication channels. These channels are characterized by random matrices that admit various statistical descriptions depending on the actual application. The goal of this paper is the investigation and application of random matrix theory with particular emphasis on the asymptotic theorems on the distribution of the squared singular values under various assumption on the joint distribution of the random matrix entries. Random matrices tend to be well conditioned, and we employ this well known property to advance matrix computations. We prove that our algorithms employing Gaussian random matrices are efficient, but in our tests the algorithms have consistently remained as powerful where we used sparse and structured random matrices, defined by much fewer random parameters. We numerically stabilize Gaussian elimination with no pivoting as well as block Gaussian elimination, precondition an ill conditioned linear system of equations, compute numerical rank of a matrix without orthogonalization and pivoting, approximate the singular spaces of an ill conditioned matrix associated with its largest and smallest singular values, and approximate this matrix with low-rank matrices, with applications to its 2-by-2 block triangulation and to tensor decomposition. Some of our results and techniques can be of independent interest, e.g., our estimates for the condition numbers of random Toeplitz and circulant matrices and our variations of the Sherman--Morrison--Woodbury formula. Abstract Let X 1 , … , X N ∈ R n be independent centered random vectors with log-concave distribution and with the identity as covariance matrix. We show that with overwhelming probability one has sup x ∈ S n − 1 | 1 N ∑ i = 1 N ( | 〈 X i , x 〉 | 2 − E | 〈 X i , x 〉 | 2 ) | ⩽ C n N , where C is an absolute positive constant. This result is valid in a more general framework when the linear forms ( 〈 X i , x 〉 ) i ⩽ N , x ∈ S n − 1 and the Euclidean norms ( | X i | n ) i ⩽ N exhibit uniformly a sub-exponential decay. As a consequence, if A denotes the random matrix with columns ( X i ) , then with overwhelming probability, the extremal singular values λ min and λ max of A A ⊤ satisfy the inequalities 1 − C n N ⩽ λ min N ⩽ λ max N ⩽ 1 + C n N which is a quantitative version of Bai–Yin theorem (Z.D. Bai, Y.Q. Yin, 1993 [4] ) known for random matrices with i.i.d. entries. Marginal (contingency) tables are the method of choice for government agencies releasing statistical summaries of categorical data. In this paper, we derive lower bounds on how much distortion (noise) is necessary in these tables to ensure the privacy of sensitive data. We extend a line of recent work on impossibility results for private data analysis [9, 12, 13, 15] to a natural and important class of functionalities. Consider a database consisting of n rows (one per individual), each row comprising d binary attributes. For any subset of T attributes of size |T|=k, the marginal table for T has 2k entries; each entry counts how many times in the database a particular setting of these attributes occurs. We provide lower bounds for releasing all d k k-attribute marginal tables under several different notions of privacy. (1) We give efficient polynomial time attacks which allow an adversary to reconstruct sensitive information given insufficiently perturbed marginal table releases. In particular, for a constant k, we obtain a tight bound of Ω(min √n, √dk-1) on the average distortion per entry for any mechanism that releases all k-attribute marginals while providing "attribute" privacy (a weak notion implied by most privacy definitions). (2) Our reconstruction attacks require a new lower bound on the least singular value of a random matrix with correlated rows. Let M(k) be a matrix with d k rows formed by taking all possible k-way entry-wise products of an underlying set of d random vectors from 0,1 n. For constant k, we show that the least singular value of M(k) is Ω(√dk) with high probability (the same asymptotic bound as for independent rows). (3) We obtain stronger lower bounds for marginal tables satisfying differential privacy. We give a lower bound of Ω(min √n, √ dk), which is tight for n Ω (dk). We extend our analysis to obtain stronger results for mechanisms that add instance-independent noise and weaker results when k is super-constant. Abstract Given an m × n matrix A and a positive integer k, we describe a randomized procedure for the approximation of A with a matrix Z of rank k. The procedure relies on applying A T to a collection of l random vectors, where l is an integer equal to or slightly greater than k; the scheme is efficient whenever A and A T can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as l m times the ( k + 1 ) st greatest singular value σ k + 1 of A, with negligible probability of even moderately large deviations. The actual estimates derived in the paper are fairly complicated, but are simpler when l − k is a fixed small nonnegative integer. For example, according to one of our estimates for l − k = 20 , the probability that the spectral norm ‖ A − Z ‖ is greater than 10 ( k + 20 ) m σ k + 1 is less than 10 − 17 . The paper contains a number of estimates for ‖ A − Z ‖ , including several that are stronger (but more detailed) than the preceding example; some of the estimates are effectively independent of m. Thus, given a matrix A of limited numerical rank, such that both A and A T can be applied rapidly to arbitrary vectors, the scheme provides a simple, efficient means for constructing an accurate approximation to a singular value decomposition of A. Furthermore, the algorithm presented here operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples. We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D* of rank at most k so that holds with probability at least 1 − Δ (where v·vF is the Frobenius norm). The algorithm takes time polynomial in k,1 e, log(1 Δ) only and is independent of m and n. In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation. Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times, especially after the pioneering works of Emmanuel Cand e s and collaborators. This paper introduces a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has "a little bit of structure." Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to solve problems related to low rank matrix estimation, blockmodels, distance matrix completion, latent space models, positive definite matrix completion, graphon estimation and generalized Bradley--Terry models for pairwise comparison. We present a randomized iterative algorithm that exponentially converges in the mean square to the minimum @math -norm least squares solution of a given linear system of equations. The expected number of arithmetic operations required to obtain an estimate of given accuracy is proportional to the squared condition number of the system multiplied by the number of nonzero entries of the input matrix. The proposed algorithm is an extension of the randomized Kaczmarz method that was analyzed by Strohmer and Vershynin. In this note, we establish some bounds on the supremum of certain empirical processes indexed by sets of functions with the same L2 norm. We present several geometric applications of this result, the most important of which is a sharpening of the Johnson–Lindenstrauss embedding Lemma. Our results apply to a large class of random matrices, as we only require that the matrix entries have a subgaussian tail. Subsampled (or partial) Fourier matrices were originally introduced in the compressive sensing literature by Later, in papers by Candes and Tao and Rudelson and Vershynin, it was shown that (random) subsampling of the rows of many other classes of unitary matrices also yield effective sensing matrices. The key requirement is that the rows of U, the unitary matrix, must be highly incoherent with the basis in which the signal is sparse. In this paper, we consider acquisition systems that — despite sensing sparse signals in an incoherent domain — cannot randomly subsample rows from U. We consider a general class of systems in which the sensing matrix corresponds to subsampling of the rows of matrices of the form Φ = RU (instead of U), where R is typically a low-rank matrix whose structure reflects the physical technological constraints of the acquisition system. We use the term “structurally-subsampled unitary matrices” to describe such sensing matrices. We investigate the restricted isometry property of a particular class of structurally-subsampled unitary matrices that arise naturally in application areas such as multiple-antenna channel estimation and sub-nyquist sampling. In addition, we discuss an immediate application of this work in the area of wireless channel estimation, where the main results of this paper can be applied to the estimation of multiple-antenna orthogonal frequency division multiplexing channels that have sparse impulse responses. This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory. The harmonic Lanczos bidiagonalization method can be used to compute the smallest singular triplets of a large matrix @math . We prove that for good enough projection subspaces harmonic Ritz values converge if the columns of @math are strongly linearly independent. On the other hand, harmonic Ritz values may miss some desired singular values when the columns of @math are almost linearly dependent. Furthermore, harmonic Ritz vectors may converge irregularly and may even fail to converge. Based on the refined projection principle for large matrix eigenproblems due to the first author, we propose a refined harmonic Lanczos bidiagonalization method that takes the Rayleigh quotients of the harmonic Ritz vectors as approximate singular values and extracts the best approximate singular vectors, called the refined harmonic Ritz approximations, from the given subspaces in the sense of residual minimizations. The refined approximations are shown to converge to the desired singular vectors once the subspaces are sufficiently good and the Rayleigh quotients converge. An implicitly restarted refined harmonic Lanczos bidiagonalization algorithm (IRRHLB) is developed. We study how to select the best possible shifts, and suggest refined harmonic shifts that are theoretically better than the harmonic shifts used within the implicitly restarted harmonic Lanczos bidiagonalization algorithm (IRHLB). We propose a novel procedure that can numerically compute the refined harmonic shifts efficiently and accurately. Numerical experiments are reported that compare IRRHLB with five other algorithms based on the Lanczos bidiagonalization process. It appears that IRRHLB is at least competitive with them and can be considerably more efficient when computing the smallest singular triplets.