# Tail Bounds forℓ1 Norm of Gaussian Random Matrices with Applications

Authors: Xianjie Gao; Mingliang Zhang; Jinming Luo
Journal: Journal of Mathematics
 (2022)

---

## Abstract

As major components of the random matrix theory, Gaussian random matrices have been playing an important role in many fields, because they are both unitary invariant and have independent entries and can be used as models for multivariate data or multivariate phenomena. Tail bounds for eigenvalues of Gaussian random matrices are one of the hot study problems. In this paper, we present tail and expectation bounds for theℓ1 norm of Gaussian random matrices, respectively. Moreover, the tail and expectation bounds for the ℓ1 norm of the Gaussian Wigner matrix are calculated based on the resulting bounds. Compared with existing results, our results are more suitable for the high-dimensional matrix case. Finally, we study the tail bounds for the parameter vector of some existing regularization algorithms.


---

## Body

## 1.  Introduction

The random matrix theory (RMT) has developed into an important field of probability theory. RMT has been used in many disciplines, e.g., high-dimensional data analysis [1], neural networks [2], the matrix low-rank approximation [3], compressed sensing [4], dimension reduction [5], combinatorial optimization [6], deep learning [7], wireless communications [8], multiview unsupervised feature selection [9], local and global problems of random matrices [10], multiview subspace clustering [11], and feature selective projection [12].The research on tail bounds for sums of random matrices can be traced back to the Ahlswede–Winter method [13]. Tropp [14] achieved tighter results and proposed a user-friendly tail behavior for sums of random matrices. To conquer the influence of the matrix dimension, tail bounds dependent on the intrinsic dimension have been proposed [15, 16]. Zhang et al. [17] presented the dimension-free tail bounds of the largest singular value for sums of random matrices. Gao et al. [18] obtained dimension-free bounds for the largest singular values of matrix Gaussian series. There have also been studies on the small-deviation behavior of random matrices [19, 20].


### 1.1.  Related Works

LetG be a d1×d2 Gaussian random matrix, whose entries are independent standard normal variables. Let ⊙ denote the Hadamard product of matrices. This means G can be represented as the Hadamard product of two matrices:(1)G=G⊙A,where the dimension of the matrix A is the same as that of G, whose entries are 1. According to Corollary 4.2 in [14] and assumption d1≥d2 (in this paper, unless otherwise specified, the assumption d1≥d2 is satisfied), we can obtain that for any t>0,(2)ℙG≥t≤d1+d2⋅e−t2/2d1.The symbolG represents the spectral norm of G.According to Theorem 2 in [18], we can obtain that for any t>0,(3)ℙσ1G≥t≤2d1d2⋅e−t2/2d1d2.The symbolσ1G represents the largest singular value (LSV) of G.The expectation bound is derived from Theorem 4.6.1 in [21] for the spectral norm of G:(4)EG≤2d1logd1+d2.For the LSV ofG, the expectation bound can be obtained from Theorem 4 in [18]:(5)Eσ1G≤d1d22log2.However, to the best of our knowledge, there is little work on the tail bounds for theℓ1 norm of Gaussian random matrices.


### 1.2.  Overview of Main Results

Gaussian random matrices are used in many fields, e.g., signal processing and combinatorial optimization. In order to supplement and improve the theoretical research of random matrix concentration inequalities, in this paper, we present tail bounds for theℓ1 norm of Gaussian random matrices, i.e., the upper bound of(6)ℙGℓ1≥t.The symbolGℓ1 represents the ℓ1 norm of G. We also obtain the expectation bounds for the ℓ1 norm of Gaussian random matrices EGℓ1. According to the definition of the ℓ1 norm, our results are obtained based on the Laplace-transform method of the folded Gaussian distribution. As applications, we use the obtained theorem to compute the tail and the expectation bounds for the ℓ1 norm of the Gaussian Wigner matrix. In contrast to the existing results, our results are more suitable for the high-dimensional matrix case.The rest of this paper is organized as follows. Section2 introduces some preliminary knowledge on the ℓ1 norm and folded Gaussian distribution. Section 3 gives the tail and expectation bounds for the ℓ1 norm of Gaussian random matrices and presents the application of our results in the study of the Gaussian Wigner matrix. In Section 4, we study the tail bounds for the parameter vector of some existing regularization algorithms. The last section concludes the paper.


## 1.1.  Related Works

LetG be a d1×d2 Gaussian random matrix, whose entries are independent standard normal variables. Let ⊙ denote the Hadamard product of matrices. This means G can be represented as the Hadamard product of two matrices:(1)G=G⊙A,where the dimension of the matrix A is the same as that of G, whose entries are 1. According to Corollary 4.2 in [14] and assumption d1≥d2 (in this paper, unless otherwise specified, the assumption d1≥d2 is satisfied), we can obtain that for any t>0,(2)ℙG≥t≤d1+d2⋅e−t2/2d1.The symbolG represents the spectral norm of G.According to Theorem 2 in [18], we can obtain that for any t>0,(3)ℙσ1G≥t≤2d1d2⋅e−t2/2d1d2.The symbolσ1G represents the largest singular value (LSV) of G.The expectation bound is derived from Theorem 4.6.1 in [21] for the spectral norm of G:(4)EG≤2d1logd1+d2.For the LSV ofG, the expectation bound can be obtained from Theorem 4 in [18]:(5)Eσ1G≤d1d22log2.However, to the best of our knowledge, there is little work on the tail bounds for theℓ1 norm of Gaussian random matrices.


## 1.2.  Overview of Main Results

Gaussian random matrices are used in many fields, e.g., signal processing and combinatorial optimization. In order to supplement and improve the theoretical research of random matrix concentration inequalities, in this paper, we present tail bounds for theℓ1 norm of Gaussian random matrices, i.e., the upper bound of(6)ℙGℓ1≥t.The symbolGℓ1 represents the ℓ1 norm of G. We also obtain the expectation bounds for the ℓ1 norm of Gaussian random matrices EGℓ1. According to the definition of the ℓ1 norm, our results are obtained based on the Laplace-transform method of the folded Gaussian distribution. As applications, we use the obtained theorem to compute the tail and the expectation bounds for the ℓ1 norm of the Gaussian Wigner matrix. In contrast to the existing results, our results are more suitable for the high-dimensional matrix case.The rest of this paper is organized as follows. Section2 introduces some preliminary knowledge on the ℓ1 norm and folded Gaussian distribution. Section 3 gives the tail and expectation bounds for the ℓ1 norm of Gaussian random matrices and presents the application of our results in the study of the Gaussian Wigner matrix. In Section 4, we study the tail bounds for the parameter vector of some existing regularization algorithms. The last section concludes the paper.


## 2.  Notations and Preliminaries

In this section, we provide some preliminary knowledge on theℓ1 norm of matrices and the folded Gaussian distribution.


### 2.1.  Theℓ1 Norm of Matrices

For ad1×d2 matrix B, the entrywise ℓ1 norm of a matrix is defined as(7)Bℓ1=∑i=1d1∑j=1d2bij,where bij is the entry of B. The ℓ1 norm is an optimal convex approximation to the ℓ0 norm, so it can also represent sparsity and makes the model easier to interpret. The ℓ1 norm is widely used in machine learning and its related fields, e.g., low-rank approximation [22] and dictionary learning [23].


### 2.2.  Folded Gaussian Distribution

The folded Gaussian distribution is the absolute value of a random variable with a normal distribution, which is widely applied in many aspects, especially in Bayesian inference applications [24] and process capability measures [25]. Given a standard normal variable γ, the random variable x=γ is subject to the folded Gaussian distribution. The probability density function (PDF) is given by(8)fxγ=2πe−γ2/2,for γ≥0, and 0 everywhere else.The moment generating function (mgf) is given by(9)Eeθx=2eθ2/21−Φ−θ,∀θ∈ℝ,where Φ is the normal cumulative distribution function:(10)Φξ=121+erfξ2,where the erf⋅ is the error function (the error function is defined as: erfz=2/π∫0ze−t2dt).Since−1<erf⋅<1, then, there exists c>0 such that(11)Eeθx=2eθ2/21−Φ−θ,=eθ2/21−erf−θ2,=eθ2/21+erfθ2,≤2eθ2/2≤ecθ2.The third inequality holds because theerf⋅ is an odd function.


## 2.1.  Theℓ1 Norm of Matrices

For ad1×d2 matrix B, the entrywise ℓ1 norm of a matrix is defined as(7)Bℓ1=∑i=1d1∑j=1d2bij,where bij is the entry of B. The ℓ1 norm is an optimal convex approximation to the ℓ0 norm, so it can also represent sparsity and makes the model easier to interpret. The ℓ1 norm is widely used in machine learning and its related fields, e.g., low-rank approximation [22] and dictionary learning [23].


## 2.2.  Folded Gaussian Distribution

The folded Gaussian distribution is the absolute value of a random variable with a normal distribution, which is widely applied in many aspects, especially in Bayesian inference applications [24] and process capability measures [25]. Given a standard normal variable γ, the random variable x=γ is subject to the folded Gaussian distribution. The probability density function (PDF) is given by(8)fxγ=2πe−γ2/2,for γ≥0, and 0 everywhere else.The moment generating function (mgf) is given by(9)Eeθx=2eθ2/21−Φ−θ,∀θ∈ℝ,where Φ is the normal cumulative distribution function:(10)Φξ=121+erfξ2,where the erf⋅ is the error function (the error function is defined as: erfz=2/π∫0ze−t2dt).Since−1<erf⋅<1, then, there exists c>0 such that(11)Eeθx=2eθ2/21−Φ−θ,=eθ2/21−erf−θ2,=eθ2/21+erfθ2,≤2eθ2/2≤ecθ2.The third inequality holds because theerf⋅ is an odd function.


## 3.  Main Results

In this section, we present the tail and the expectation bounds for theℓ1 norm of Gaussian random matrices and use our theoretical findings to compute the tail and the expectation bounds of the Gaussian Wigner matrix.


### 3.1.  Bounds for Gaussian Random Matrices

Based on the mgf bound (11), we first obtain the tail bound for the ℓ1 norm of Gaussian random matrices.Theorem 1.
LetG be a Gaussian random matrix with dimension d1×d2. That is, its entries are independent standard normal variables. Then there holds that for any t>0,(12)ℙGℓ1≥t≤e−t2/4cd1d2.Proof.
For any positive numberθ, we have(13)ℙGℓ1≥t=ℙeθ∑i=1d1∑j=1d2γij≥eθt≤e−θt⋅Eeθ∑i=1d1∑j=1d2γij≤e−θt⋅∏i=1d1∏j=1d2Eeθ|γij|≤exp−θt+cd1d2θ2≤e−t2/4cd1d2.
The first identity uses the monotonicity of the scalar exponential function and the second relation is Markov’s inequality. The infimum is attained whenθ=t/2cd1d2, and this completes the proof.Compared with the previous result (2), the tail bound (12) has no dimensional coefficient term. Therefore, the tail bound (12) is more applicable for the case of high-dimensional matrices and does not need intrinsic dimension to optimize the result. Compared with the existing result (3), our results are less affected by dimension.Based on Theorem1, we can obtain the expectation bound for the ℓ1 norm of Gaussian random matrices.Theorem 2.
Given a Gaussian random matrixG, then there holds that(14)EGℓ1≤2cd1d2.Proof.
According to Theorem1, we have(15)EGℓ12=∫0+∞ℙGℓ1≥tdt≤4cd1d2.
According to Jensen’s inequality, we have(16)EGℓ1≤2cd1d2.
This completes the proof.Note that the second bound (14) is tighter than the previous result (5). This becomes more and more apparent as the dimension of the matrix increases.


### 3.2.  Gaussian Wigner Matrix

As an application, we use our resulting bounds to compute the tail and expectation bounds for theℓ1 norm of the Gaussian Wigner matrix.Consider a Gaussian Wigner matrixW∈ℝd×d in the following form:(17)W=0γ12γ13⋯γ1dγ120γ23⋯γ2dγ13γ230⋯γ3d⋮⋮⋮⋱⋮γ1dγ2dγ3d⋯0,where γjk1≤j<k≤d are independent standard normal variables.The research on the large deviation principle for the Gaussian Wigner matrix is a classic problem in the random matrix theory [26–28]. Next, based on our resulting bounds, we compute the tail and expectation bounds for the ℓ1 norm of W as follows. For any t>0,(18)ℙWℓ1≥t≤e−t2/4cdd−1;by Theorem1,(19)EWℓ1≤2cdd−1;by Theorem2.Compared with the previous result (17) (ℙσ1W≥t≤2dd−1/2e−t2/dd−1) in [18], the tail bound (18) has no dimensional coefficient term 2dd−1/2. Note that the second bound (19) is tighter than the previous result (19) (Eσ1W≤dd−1/22log2) in [18]. Therefore, our bounds are more applicable for the case of high-dimensional matrices.


## 3.1.  Bounds for Gaussian Random Matrices

Based on the mgf bound (11), we first obtain the tail bound for the ℓ1 norm of Gaussian random matrices.Theorem 1.
LetG be a Gaussian random matrix with dimension d1×d2. That is, its entries are independent standard normal variables. Then there holds that for any t>0,(12)ℙGℓ1≥t≤e−t2/4cd1d2.Proof.
For any positive numberθ, we have(13)ℙGℓ1≥t=ℙeθ∑i=1d1∑j=1d2γij≥eθt≤e−θt⋅Eeθ∑i=1d1∑j=1d2γij≤e−θt⋅∏i=1d1∏j=1d2Eeθ|γij|≤exp−θt+cd1d2θ2≤e−t2/4cd1d2.
The first identity uses the monotonicity of the scalar exponential function and the second relation is Markov’s inequality. The infimum is attained whenθ=t/2cd1d2, and this completes the proof.Compared with the previous result (2), the tail bound (12) has no dimensional coefficient term. Therefore, the tail bound (12) is more applicable for the case of high-dimensional matrices and does not need intrinsic dimension to optimize the result. Compared with the existing result (3), our results are less affected by dimension.Based on Theorem1, we can obtain the expectation bound for the ℓ1 norm of Gaussian random matrices.Theorem 2.
Given a Gaussian random matrixG, then there holds that(14)EGℓ1≤2cd1d2.Proof.
According to Theorem1, we have(15)EGℓ12=∫0+∞ℙGℓ1≥tdt≤4cd1d2.
According to Jensen’s inequality, we have(16)EGℓ1≤2cd1d2.
This completes the proof.Note that the second bound (14) is tighter than the previous result (5). This becomes more and more apparent as the dimension of the matrix increases.


## 3.2.  Gaussian Wigner Matrix

As an application, we use our resulting bounds to compute the tail and expectation bounds for theℓ1 norm of the Gaussian Wigner matrix.Consider a Gaussian Wigner matrixW∈ℝd×d in the following form:(17)W=0γ12γ13⋯γ1dγ120γ23⋯γ2dγ13γ230⋯γ3d⋮⋮⋮⋱⋮γ1dγ2dγ3d⋯0,where γjk1≤j<k≤d are independent standard normal variables.The research on the large deviation principle for the Gaussian Wigner matrix is a classic problem in the random matrix theory [26–28]. Next, based on our resulting bounds, we compute the tail and expectation bounds for the ℓ1 norm of W as follows. For any t>0,(18)ℙWℓ1≥t≤e−t2/4cdd−1;by Theorem1,(19)EWℓ1≤2cdd−1;by Theorem2.Compared with the previous result (17) (ℙσ1W≥t≤2dd−1/2e−t2/dd−1) in [18], the tail bound (18) has no dimensional coefficient term 2dd−1/2. Note that the second bound (19) is tighter than the previous result (19) (Eσ1W≤dd−1/22log2) in [18]. Therefore, our bounds are more applicable for the case of high-dimensional matrices.


## 4.  Analysis of Regularization Algorithms

Now that the comparison of tail bounds for different norms has been established, we will study the tail bounds for the parameter vector of some existing regularization algorithms. More precisely, we will analyse two well-known regularization algorithms for machine learningℓ1 and ℓ2 regularization algorithms.Given a sample setD=x1,y1,x1,y1,…,xN,yN, where x∈ℝI and y∈ℝ. We consider the following linear regression model:(20)minβ12∑n=1Nyn−xn,β+β02,where ⋅,⋅ denotes the inner product, β∈ℝI is the weight vector (weight matrix: 1 column, I rows), and β0∈ℝ is the bias. The model is prone to overfitting and has a low tolerance for noisy information. To overcome these shortcomings, a regularization term is added to the objective function:(21)minβ12∑n=1Nyn−xn,β+β02+λΩβ,where λ>0 is the regularization coefficient. Typically, the regularization can be set to Ω1β=β22 or Ω2β=β1. The linear regression model with Ω1β is called ridge regression [29] and with Ω2β is the least absolute shrinkage and selection operator (Lasso) [30].As shown in Figure1, the solution of Lasso usually contains some 0 components, i.e., the weight vector is sparse. Therefore, Lasso has become one of the most popular methods for feature extraction and has been successfully applied to many practical problems [31–34].Figure 1
Geometric explanation of lasso and ridge regression.
(a)(b)The aim is to find aβ∗ that minimizes the objective function. The error bound with respect to the parameters is the supremum(22)supβ−β∗,with an alternative probability expression(23)ℙsupβ−β∗≥t.In machine learning, the weight initialization method has a crucial impact on the convergence rate of the model and the quality of model performance. The Gaussian initialization method is the simplest initialization method, which is to initialize the weights according to a Gaussian distribution. Through the tail bound of Section3, we know that the tail bound for the ℓ1 norm of Gaussian random matrices is tighter than the tail bound for the ℓ2 norm. Actually, the difference between ℓ1 and ℓ2 is that the minimization process is different. As shown in Figure 2, ℓ1 descends according to the absolute value function, while ℓ2 descends according to the quadratic function. The falling speed of ℓ1 is faster than that of ℓ2 near the 0,0 point.Figure 2
Descent speed of lasso and ridge regression.


## 5. Conclusion

In this paper, we present the tail bound for theℓ1 norm of Gaussian random matrices. In particular, we also give the expectation bound for the ℓ1 norm of Gaussian random matrices. As an application, we use our resulting bounds to compute the tail and expectation bounds for the ℓ1 norm of the Gaussian Wigner matrix. In contrast to the existing results, our results are more suitable for the high-dimensional matrix case. Finally, we study the tail bounds for the parameter vector of ℓ1 and ℓ2 regularization algorithms.In future work, we will apply the theoretical results to some potential practical scenarios, such as clustering and classification.



---

*Source: 1456713-2022-07-08.xml*