{'fraction_non_alphanumeric': 0.040788171430285215, 'fraction_numerical': 0.011786581891251537, 'mean_word_length': 4.288501189532117, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Enhanced Expressive Power and Fast Training of Neural Networks by Random Projections

Random projections are able to perform dimension reduction efficiently for datasets with nonlinear low-dimensional structures. One well-known example is that random matrices embed sparse vectors into a low-dimensional subspace nearly isometrically, known as the restricted isometric property in compressed sensing. In this paper, we explore some applications of random projections in deep neural networks. We provide the expressive power of fully connected neural networks when the input data are sparse vectors or form a low-dimensional smooth manifold. We prove that the number of neurons required for approximating a Lipschitz function with a prescribed precision depends on the sparsity or the dimension of the manifold and weakly on the dimension of the input vector. The key in our proof is that random projections embed stably the set of sparse vectors or a low-dimensional smooth manifold into a low-dimensional subspace. Based on this fact, we also propose some new neural network models, where at each layer the input is first projected onto a low-dimensional subspace by a random projection and then the standard linear connection and non-linear activation are applied. In this way, the number of parameters in neural networks is significantly reduced, and therefore the training of neural networks can be accelerated without too much performance loss.


Introduction
Over the past few years, learning via multiple-layer neural network has been widely studied and has achieved unprecedented success. It has many important applications in image recognition, speech recognition, and natural language processing.
One of the fundamental theoretical question in deep learning is the expressive power of a neural network, which describes its ability to approximate functions. The celebrated universal approximation theorem, which was proved by Cybenko [9], Hornick [16] et al, Funahashi [14] and Barron [3], states that sufficiently large shallow (that is, depth-2 or equivalently, one hidden layer) neural networks can approximate any continuous function on a bounded domain to arbitrary accuracy. But the required size of such networks can be exponentially increasing with respect to the dimension. Indeed, Eldan and Shamir [10] proved that there is a continuous function expressed by a small depth-3 feedforward neural networks which cannot be approximated by any shallow network to more than a certain constant accuracy, unless its width grows exponentially in the dimension. This shows the power of depth for feedforward neural network.
Lu-Pu-Wang-Hu-Wang [17] studied the expressive power of neural networks from the width point of view. They shown that there exists a class of width-O(k 2 ) shallow ReLU network that cannot be approximated by any width-O(k 1.5 ) and depth-k neural network.
However, the data input in the real world applications are usually structured. For example, images modelled as piecewise smooth functions can have sparse representations under certain orthonormal bases or frames [19]. This means that the intrinsic dimension of the input data is significantly smaller than the ambient space dimension. This fact is often ignored in aforementioned classical approximation results. The expressive power of a neural network may be improved by exploring the structure of the input data. In this direction, Shaham-Cloninger-Coifman [28] studied approximations of functions on a smooth kdimensional submanifold embedded in R d . They constructed a depth-4 network and controlled the error of its approximation, where the size of their network depends on k but just weakly on d. Chui-Lin-Zhou [8] studied the expressive power of neural networks in the regression setting when the samples are located approximately on some unknown manifold. They showed that the error of the approximation of their trained depth-3 neural network to the regression function depends on the number of samples, and the dimension of the manifold instead of the ambient dimension.
In this paper, we consider a different approach to analyze the theoretical performance of neural networks with structured input data. Based on our analysis, we propose a new architecture of neural networks, for which the training can be significantly accelerated compared to conventional fully connected or convolutional neural networks. Our main idea is to use linear random projections developed in compressed sensing [13].
For simplicity, we assume that the input data are sparse vectors, namely, k-sparse vectors in R d . Using the theory of compressed sensing, one can construct a random projection onto an O(k log(d/k))dimensional space that satisfies the so-called restricted isometric property (RIP), saying that the random projection is nearly isometric when restricted to sparse vectors. Therefore, to get an efficient function approximation, we can first compress the sparse high-dimensional input vectors to low-dimensional ones without changing the metric too much, and then apply a standard neural network with low-dimensional vectors as inputs. In this way, the expressive power is the same as that of the neural network with O(k log(d/k))dimensional input. In other words, we obtain neural networks with expressive power depending on k and weakly on d. Contrary to the work in [8,28], the neural networks we constructed can be very deep with a fixed width. Our approach works not only for sparse inputs but also for a large class of structures of input data, for example, when the input data are sampled from a low dimensional manifold.
The idea of using random projection can also be incorporated into fully connected and convolutional neural networks to get new architectures for multi-layer neural networks. At each layer, we first apply a random projection to capture the intrinsic data structure, and then the standard linear transform and nonlinear activation follow. This will improve the overall computational efficiency of the neural networks, since the number of parameters are significantly reduced. In particular, compared to standard fully connected and convolutional neural networks, the training is accelerated drastically. We will also demonstrate the new neural network can achieve comparable accuracy to the original ones.
The rest of this paper is organized as follows. In Section 2, we give a brief introduction to random projections and their stable embedding. In Section 3, we present our theoretical results on the expressive power of neural networks for structured input data. In Section 4, we incorporate random projections into each layer of full connected and convolutional neural networks to get better architecture of deep neural networks. Section 5 is devoted to numerical experiments demonstrating the efficiency and effectiveness of the resulting neural networks.

Random Projections and the Restrictive Isometry Property
We will use random projections to study the expressive power and accelerate the training of neural networks. Random projections are able to embed datasets with a non-linear low-dimensional structure into a lowdimensional subspace while almost keeping the metric. In this section, we give a review on related results.

Compressed Sensing and RIP
Compressed sensing [6,13] is a signal processing technique that enables acquiring compressible signals from a much smaller number of linear samples than the ambient dimension of signals. It has numerous applications in imaging [6,18,25]. Compressed sensing takes advantage of the fact that most signals of interest in practice are compressible: there are only a few nonzero or big elements when the signals are represented over a certain dictionary such as wavelet basis. The key concept in compressed sensing is the restricted isometric property (RIP), under which many algorithms are able to reconstruct the underlying signal stably. One of the most powerful results in compressed sensing is that some family of random matrices with very few rows will satisfy RIP with high probability.
A signal in x ∈ R d is compressible if W x 0 ≤ k for some k ≪ d for some linear transform W ∈ R m×d . Here the ℓ 0 -norm · 0 stands for the number of nonzeros of a vector. We also call such an x a k-sparse signal. In other words, a signal is compressible if it is sparse under certain linear transform. This assumption holds true for a wide variety of classes of signals. For example, piecewise smooth signals are (nearly) sparse under the representation of orthogonal wavelets or wavelet frames such as the curvelet [19]. Actually, the sparsity assumption is the foundation of many models and approaches in modern signal processing and imaging.
Since the degree of freedom in a k-sparse signal is only k with k ≪ d, it is possible to acquire the signal efficiently by n linear samples with n ≪ d. This is exploited by compressed sensing. In the encoding stage of compressed sensing, we acquire a k-sparse sparse x by b := Ax, where A ∈ R n×d is a sampling matrix with each row corresponding to one linear sample. Compared to traditional signal processing where the full sample of x is required, compressed sensing can save sampling costs significantly and can be applied to a wider range of imaging scenarios for which the full sampling is prohibited. In the decoding stage, one wants to recover the k-sparse signal x from b. Various approaches are available with recovery performance guarantee, including convex optimization based approaches [6] and non-convex ones [4,12,24]; see also the book [13] and the references therein.
A key concept in compressed sensing theory is the restricted isometric property (RIP) introduced by E. Candès and T. Tao [7]. For simplicity, we assume the sparse transform W = I, i.e., the underlying signal x satisfies x ∈ S k := {y ∈ R d : y 0 ≤ k}.
Then, to have a successful recovery of any signal x ∈ S k from b = Ax, we should at least require that the sampling operator A is injective on S k . That is, it is necessary A(x 1 − x 2 ) 2 > 0 for any x 1 , x 2 ∈ S k satisfying x 1 = x 2 . However, there will always be noise in the practical measurements, and also the injectivity may be too restrictive to design recovery algorithms. To have a stable recovery with practical algorithms, we need to relax the restricted injectivity to the following restricted isometric property (RIP): where δ s ∈ (0, 1). Here we assume A is normalized so that its restricted eigenvalues are concentrated around 1. If we choose s = 2k, then RIP (2.1) implies that, for any k-sparse vectors x 1 and x 2 , A(x 1 − x 2 ) 2 is almost the same as x 1 − x 2 2 . In other words, if A satisfies RIP, then the application of A preserves the metric of the set S k inherited from R d . This enables us to design efficient and stable algorithms for the recovery of sparse signals with a theoretical performance guarantee [4,6,12,24]. For example, it was shown that if A satisfies RIP with δ 2s < √ 2 − 1, then the solution of the following ℓ 1 -norm minimization gives a stable recovery of the k-sparse vector x where b = Ax + ǫ are the noisy linear samples of x with the noise ǫ satisfying ǫ 2 ≤ σ. Actually, even when x is not exactly in S k but only close to it, (2.2) is still able to give a faithful recovery of x.

Random Projections Satisfy RIP
An important question is then to find matrices A ∈ R n×d with good RIP constants using the smallest possible n. Since computing the RIP constants is strongly NP-hard, it is very difficult to use numerical methods to construct RIP matrices. Also, any existing deterministic matrices satisfying RIP will not have an optimal m. The best known deterministic RIP matrices have a number of rows n ≥ O(s 2 ), and it is still an open problem to construct a deterministic matrix satisfying RIP. A major breakthrough in compressive sensing is the use of random matrices to construct RIP matrices with optimal m. In particular, let A ∈ R n×d be a random matrix whose entries are independent Gaussian random variables with mean 0 and variance 1/n. Then, with overwhelming probability, . This result is summarized in the following theorem.
Theorem 2.1 (Theorem 9.2 in [13]). Let A ∈ R n×d be a random matrix whose entries are independent Gaussians with mean-0 variance-1/n. Then, there exists a universal constant C > 0 such that A satisfies The theorem was first proved in [7] with a weaker bound in a more restrictive setting, and simple proofs can be found in [1,13]. Besides random Gaussian matrices, there exist other types of random matrices satisfying RIP with n ∼ O(s log α (d)) for some α > 0, such as subGaussian, Bernoulli, and random rows of discrete Fourier transform matrices [1,13,27].
The RIP above can be extended to general cases where the sparsifying transform W is not necessarily the identity. When W ∈ R d×d is orthogonal, RIP (2.1) can be adapted to Since Gaussian random variables are unitary invariant, a simple calculation and Theorem 2.1 give that, for any orthogonal W , a Gaussian random matrix A ∈ R n×d satisfies the generalized RIP (2.3) with high probability provided n ∼ O(s log(d/s)). When W ∈ R m×d forms a tight frame (i.e., W T W = I), the generalized RIP was studied in [5,26]. Gaussian random matrices satisfy the generalized RIP there with high probability and optimal n.

RIP on Smooth Manifolds
Besides sparse signal models, there is another common model called manifold signal model. This model generalizes the notion of concise signal structure beyond the framework of bases and representations. It arises in broad cases, for example, where a k-dimensional parameter can be identified that carries the relevant information about a signal that changes as a continuous function of these parameters. In general, this dependence may not be neatly reflected in a sparse set of transform coefficients. In [2], Baraniuk and Wakin proposed a approach for nonadaptive dimensionality reduction of manifold-modeled data, where they demonstrated that a small number of random linear projections can preserve key information about a manifold-modeled signal. To state their results, we need a few definitions for a Riemannian manifold.
Let M be a k-dimensional compact Riemannian submanifold embedded in R d . The condition number is defined as 1/τ , where τ is the largest number having the following property: for every r < τ , the tubular x denotes the set of vectors normal to the tangent space at x, is embedded in R d . Given T > 0, the geodesic covering number G(T ) of M is defined as the smallest number such that there exists a finite set is the geodesic distance between a and x. We say that M has geodesic covering regularity R for resolutions where V is the volume of M.
If n ≤ d, then with probability at least 1 − ρ, the following statement holds: For every x, y ∈ M, Hence, if k ≪ d, then we reduce the dimension of input data from d to O(k log d).

Improved Expressive Power of Neural Networks by Random Projections
In this section, we use the random projections discussed in the previous section to explore the expressive power of neural networks for functions on datasets with a low-dimensional structure in the ambient space R d .

Fully-Connected Neural Networks (FCNN)
There are many artificial neural network architectures available, such as the fully-connected neural network (FCNN), the convolutional neural network (CNN), and the recurrent neural network. We will study the expressive power a multi-layer fully-connected neural network with the rectified linear unit (ReLU) as the activation function. The ReLU is so far the most popular activation function for deep neural networks, and it is the positive part of its argument. More precisely, let z ∈ R ℓ , and the ReLU is defined by Let x ∈ R d be the input. Then it generates outputs x (l) at the l-th layer recursively by: x (0) = x, and where W (l) : R d l−1 → R d l is the affine transformation at layer l. The final output y of the neural network is where W (L+1) : R d L → R is an affine transformation. Therefore, the function represented by the fullyconnected neural network is The number L is usually called the depth of the network, and the d l 's are called the widths. The sum L l=1 d l is called the number of neurons of the network. If L = 1, then the network is called a shallow neural network. If L > 1, it is called a deep neural network.

Expressive Power of Neural Networks
As mentioned in the introduction, by the celebrated universal approximation theorem, we know that sufficiently large shallow neural networks can approximate any continuous function on a bounded domain to arbitrary accuracy. That is, for a continuous function f ∈ C([−1, 1] d ) and for every ε > 0, there exists a shallow ReLU neural network f ε such that However, the universal approximation theorem does not tell the number of neurons that f ε has, or equivalently the approximation accuracy. There have been many literatures on studying the number of neurons, or the approximation accuracy, of (either shallow or deep) neural networks since the work [3] by Barron, and we know now that the number of neurons that the neural network f ε needs will depend on the regularity (e.g., the modulus continuity) of the function f .
Barron [3] first gave a quantitative approximation rate in L 2 norm for shallow neural networks, assuming the function f has bounded first moment of the magnitude of the Fourier transform. If f is r times differentiable, then Mhaskar [21] obtained an optimal quantitative approximation rate in L 2 norm, that is, for every ε > 0, there exists a shallow neural network f ε with O(ε −d/r ) neurons such that If f is C 2 and has bounded Hessian, then Shaham-Cloninger-Coifman [28] proved the same quantitative approximation rate in L ∞ norm. Their result also holds if f is supported in a lower dimensional manifold. In a recent work [15] of Hanin, several approximation results of ReLU neural networks were obtained for continuous functions, convex functions, and smooth functions, respectively. In particular, if f is bounded and Lipschitz continuous, then Theorem 1 in [15] tells that for every ε > 0, there exists a ReLU neural network with Cdd!ε −d neurons, where C is a positive constant depending only on the Lipschitz constant of f and is independent of d, such that Recall that a function f : where x − y 2 is the distance between x and y in R d . If f is Lipschitz continuous, then Lip(f ) defined above is called the Lipschitz constant. Note that Theorem 1 in [15] is stated for positive functions, but it is clearly true for bounded function as well by subtracting a large constant from the neural network.

Improved Expressive Power for Functions with Sparse Inputs
The aforementioned results on expressive power assumes that the domain of functions is [−1, 1] d . However, in real applications, the input data x is often structured. For example, in an image recognition task, the input data are digital images with d pixels, which obviously are not arbitrary in [−1, 1] d . By considering the structure of the input data, we expect to obtain better results on the expressive power of neural networks than results reviewed in the previous section, which ignore structures of input data. There are several approximation results taking into account the structure of the input. Shaham-Cloninger-Coifman [28] assumed that the domain of the function is a k-dimensional smooth submanifold embedded in R d and proved that the size of their constructed approximating networks depends on k but just weakly on d. In [8], Chui-Lin-Zhou used neural networks to approximate regression functions, where the training samples are located approximately on some unknown manifold. It was shown there that the error of the approximation of their trained depth-3 neural network to the regression function depends on the number of samples and the dimension of the manifold instead of the ambient dimension. In both of these two papers, multi-layer neural networks are constructed, for which each hidden layer is endowed with a specific learning task.
Here we provide an improved expressive power by assuming the sparsity of the input vectors and using random projections. Our assumption is motivated by the facts that many learning tasks are with images or audio signals as inputs and that images and audio signals have sparse representation under suitable basis. For simplicity, we assume the input vectors are in S k = {y ∈ R d : y 0 ≤ k} with k ≪ d, and the extension to the sparse case under a linear transformation (i.e., the input vectors are in S W s ) is straightforward. We will show in the below that, for Lipschitz continuous functions that are defined on S k , we can choose a neural network with Cnn!ε −n neurons, where n = O(k log(d/k)) and C is a positive constant depending only on the Lipschitz constant of f , to approximate f with accuracy ε. Our proof will make use of a theorem of McShane [20] and Whitney [30] on the extension of Lipschitz functions, which states that any Lipschitz continuous function defined on an arbitrary subset of R n can be extended to be a Lipschitz continuous function in R n with the same Lipschitz constant. (See also Theorem 3.1 in the book [11] of Evans and Gariepy.) Then inf Proof. Fix a δ ∈ (0, 1), say δ = 1/2. Theorem 2.1 implies that there exists a matrix A ∈ R n×d , where n = C 0 k log(d/k) with C 0 depending only on δ, satisfies the restricted isometric property (2.1) with constant δ. Since A satisfies RIP, the map x → Ax is a bijection from S k to Ω : where x is the unique element in S k such that Ax = y. Since f is a Lipschitz continuous on S k with Lipschitz constant Lip(f ) and A satisfies RIP, it is elementary to show that g is Lipschitz continuous on Ω with Lipschitz constant at most Lip(f )/(1−δ). Notice that Ω ⊆ R n . Then by the theorem of McShane [20] and Whitney [30], we can extend g to be a Lipschitz continuous function in R n with the same Lipschitz constant. By Theorem 1 in [15], we have that for every ε > 0, there exists a ReLU neural network g ε with at most m = Cnn!ε −n neurons such that where C > 0 depends only on R, L/(1 − δ), and is independent of n. In terms of f , we obtain which concludes the proof.

Remark 3.2.
In applications, the sparsity is usually much smaller than the dimension, i.e., k ≪ d. Then in order to have inf which is significantly smaller than exponential functions of d.

Improved Expressive Power for Functions on Smooth Manifolds
Using similar techniques, we can also improve the expressive power of FCNN with inputs from a compact k-dimensional Riemannian manifold embedded in R d . We assume that the underlying function is Lipschitz continuous, which is weaker than that in [28]. It turns out that the number of neurons required for an εapproximation in the infinity-norm depends weakly on d. Our main tool in the proof is Theorem 2.2, which states that random projections are stable embeddings.
Then inf Proof. Fix a δ ∈ (0, 1), say δ = 1/2. Theorem 2.2 implies that there exists a matrix A ∈ R n×d satisfies the restricted isometric property (2.4) with constant δ. Here, n = C 0 k log(d) with C 0 depending only on the condition number of M in R d , the volume of M and the geodesic covering regularity of M. Since A satisfies RIP, the map x → Ax is a bijection from M to Ω := {Ax | x ∈ M}. For every y ∈ Ω, define where x is the unique element in M such that Ax = y. As in the proof of Theorem 3.1, g is Lipschitz continuous on Ω with Lipschitz constant at most Lip(f )/(1 − δ) and can be extended to be a Lipschitz continuous function in R n with the same Lipschitz constant. By Theorem 1 in [15], we can conclude the proof in the same way as in the proof of Theorem 3.1.
Remark 3.4. The volume of M and the geodesic covering regularity of M do not depend on the ambient space R d , and hence, do not depend on d. In the definition of the condition number of M in R d , it appears to depend on R d . However, the dependence on d is very weak. For example, by the Nash embedding theorem [23], M can be isometrically embedded in , then the condition number of M in R d is the same as the condition number of M in R k(3k+11)/2 .

Remark 3.5.
There are examples shown in [22,29] that one pixel change will make deep neural networks misclassify natural images. Such changes induce a severe jump in the Lipschitz constant (which is defined with respect to the Euclidean distance as in Theorem 3.3). From the practical point of view, the natural distance of the input data should perhaps be the Euclidean distance rather than the geodesic distance on the manifold. That is part of the reason why the Lipschitz continuity of f in Theorem 3.3 is stated in terms of the Euclidean distance · 2 .

Accelerate the Training of Neural Networks by Random Projections
In this section, we use the random projections to accelerate the training of neural networks. We present in detail our implementation of random projections in both fully-connected and convolutional neural networks. We shall also provide estimates to demonstrate that our scheme indeed achieves significant reduction in computational complexity and number of parameters.

Fully-connected Neural Networks (FCNN)
The main idea in the proof of Theorems 3.1 and 3.3 is to use random projections to reduce the number of neurons. In practice, we will also use random projections to reduce the number of neurons and hence the number of parameters of FCNN. Consequently, the training of FCNN is significantly accelerated.
Here for simplicity, we assume that the input vectors are sparse under a suitable linear transformation, which is a common assumption for digital images and signals. It is similar when input signals are on a smooth manifold. The bulk of the computations of an FCNN comes from the matrix multiplication in each layer. Recall that a multi-layer FCNN produces outputs by where W (l) : R d l−1 → R d l−1 is an affine transformation, with d l−1 and d l respectively being the dimensions of the input x (l−1) and output x (l) . The final output is We modify (4.1) by random projection as in the following. At layer-1, the input vector x (0) = x ∈ S k is sparse. According to Theorem 2.1, if we choose a suitable n 0 , then with high probability a Gaussian random matrix A (1) ∈ R n 0 ×d 0 embeds S k to R n 0 nearly isometrically. Therefore, A (1) reduce the dimension of S k without too much information loss. We then apply an affine transformation U (1) : R n 0 → R d 1 on the embedded subspace R n 0 . In other words, we replace W (1) by U (1) • A (1) . In this way, there are only d 1 (n 0 + 1) parameters in layer-1, which is significantly smaller than d 1 (d 0 + 1) in (4.1). Since ReLU set negative entries to 0, the outputs of each layer are sparse vectors. The same parameter reduction procedure as in layer-1 is applied to each layer. In particular, at layer-l, we replace W (l) by U (l) • A (l) , where U (l) : R n l−1 → R d l is an affine transformation to be trained and A (l) ∈ R n l−1 ×d l−1 is a given matrix drawn from random Gaussian distribution. The number of parameters at layer-l is reduced from d l (d l−1 + 1) in (4.1) to d l (n l−1 + 1). Altogether, we propose the following FCNN where U (l) : R n l−1 → R d l is an affine transformation to be trained from the data, and A (l) ∈ R n l−1 ×d l−1 is a fixed matrix with entries drawn from i.i.d. random Gaussian distribution. The final output is y = W (L+1) x (L) with W (L+1) : R L → R an affine transformation to be trained. Under this scheme, the number of parameters can be significantly reduced so long as n l 's are kept small. In fact, it can be immediately calculated that the number of parameters of the original FCNN (4.1) is (d L + 1) + L l=1 (d l−1 + 1)d l , whereas that of the modified network (4.2) is (d L + 1) + L l=1 (n l−1 + 1)d l . In practice, since it is usually the case that d 1 and d l−1 are large and the input x (l) is sparse, n l−1 ≪ d l−1 can be easily satisfied. Therefore, the reduction of number of parameters by (4.2) is significant.

Convolutional Neural Networks (CNN)
Since convolution is linear in nature, it is possible to adapt our random projection scheme from FCNNs to CNNs. Again for simplicity, consider the l-th layer of a CNN with a ReLU activation: Here for i = l − 1 or l, X (i) ∈ R m×m×c i is the output tensor at the i-th layer, with height and width m, and c i number of channels; F (l) ∈ R h×h×c l−1 ×c l is a trainable tensor consisting of c l filters of height and width h and depth c l−1 . In addition, the "·" notation in the subscripts means all entries in that axis are included, for instance X (l) ··j is simply the m × m matrix at the j-th channel of the tensor X (l) , and F (l) ···j is the j-th filter at the l-th layer. We shall describe two possible modifications of the CNN by random projections.

Approach I: Direct Extension
Upon realizing that convolution is essentially a matrix multiplication acting on different patches of the input tensor, (4.3) can be rewritten more succinctly as whereX (l−1) ∈ R c l−1 h 2 ×m 2 is a matrix whose columns are vectorized h × h × c l−1 patches of X (l−1) to be convolved with the filters; F (l) ∈ R c l ×c l−1 h 2 is a matrix wherein each row is given by F ···j ) T ; X (l) ∈ R c l ×m 2 is the matrix whose rows are vectorized channels of X (l) , namely X (l) j· = vec(X (l) ··j ) T . As argued in the previous section, columns ofX (l−1) are sparse. Therefore, following (4.2), instead of F (l) , we first do dimension reduction of the sparse vectors by a random Gaussian matrix A (l) , followed by a linear transformation U (l) in the reduced subspace. We obtain X (l) = ReLU U (l) A (l)X (l−1) , (4.5) where, similar to the FCNN scheme, U (l) ∈ R c l ×n l−1 is trainable, and A (l) ∈ R n l−1 ×c l−1 h 2 is a fixed matrix whose entries are drawn from i.i.d. random Gaussian distribution. The effect of the larger variance of A (l) can be nullified by batch normalization. Similar to the FCNN case, the number of parameters has been reduced because of the approximation F (l) by U (l) A (l) with a small n l−1 .

Approach II: Per-channel Extension
In the first approach, columns in A (l) that correspond to one channel of the input tensor are independent from those corresponding to another. In other words, different channels of the input tensor are essentially assigned different "A"s. This means that the scheme does not take into account the correlations amongst the input channels, however in practice, for instance, the RGB channels of an input image are closely related. As a result, this might diminish the expressive power of the network. To remedy this, we can consider apply random projections separately for each channel, and then perform a summation over all the per-channel outputs. LetX (l−1) ∈ R h 2 ×m 2 ×c l−1 be the tensor such that the columns ofX (l−1) ··j are vectorized h × h patches from the j-th channel of X (l−1) . Then our modified scheme can be written as whereÛ (l) ∈ R c l ×n l−1 ×c l−1 is trainable, andÂ (l) ∈ R n l−1 ×h 2 is a given matrix whose entries are randomly drawn from i.i.d. Gaussian distribution. A small price for this approach is an increase in computational and model complexity compared to the first approach (4.5), but it still achieves substantial, albeit less dramatic, reduction over the original CNN (4.3) as long as n l−1 is small.

Experiments
In this section, we demonstrate that our schemes in Section 4 indeed achieve significant reduction in model and computational complexity while causing minimal loss in classification accuracy.  Table 1: The specifications of the models used in the experiment. "INPUT" refers to the input layer (no operation is performed here). "FC d" means fully-connected layer with d hidden units. "hxh CONV c" is a convolutional layer with filter size h and c output channels. "hxh MP" is a max-pooling layer with filter size h. "BN" is a batch normalization layer. "ReLU" is the rectified linear unit.
We used two well-known data sets, MNIST and CIFAR-10. MNIST is a collection of 28 × 28 images of handwritten digits from 0 to 9, in which there are 60,000 training examples 10,000 testing ones. CIFAR-10 consists of 32 × 32 × 3 images, where 3 indicates the three RGB channels, and there are 50,000 training examples and 10,000 test ones in this data set. The experiments were conducted using the TensorFlow framework. The specifications of the models are detailed in Table 1. We used stochastic gradient descent with 0.9 momentum for training FCNNs, and Adam optimization algorithm for CNNs. A suitable initial learning rate was chosen for each experiment and halved every 2,400 steps. All models were trained for 20 epochs and the results are summarized in Table 2. We see that with a sufficiently large n l = n our modified models use significantly small parameters and computational cost while achieving similar results.  Table 2: The model errors and complexities under various configurations. "Original" means no RP scheme is applied. "FLOPs" counts the number of multiplications and additions in the model, and "Parameters" is the number of parameters. Note that "FLOPs" and "Parameters" do not take into account biases, BN, the last layer in FCNNs (which computes the predicted probabilities), or the FC layers in CNNs. We choose n l = n for all n.