Let n < N be natural numbers. A set of vectors X 1 , . . . , X N ∈ R n is called a frame if
for all x ∈ R n . Here R ≥ 1 is an absolute constant called the frame constant, and K(n, N ) > 0 is some function of n and N . The notation ∥x∥ 2 stands for the Euclidean norm of the vector x = (x 1 , . . . , x n ):
In the last 40 years, frame theory became a well-developed area of applied mathematics, see [4], [5], [6], and the references therein. A frame can intuitively be regarded as overcomplete basis in R n . Because of this property, frames became a valuable tool in signal transmission. A signal which is viewed as an n-dimensional vector can be encoded by the sequence of its inner products with the frame vectors. If this sequence is transmitted over a communication line, then the original signal can be reconstructed even if part of the coefficients is lost or corrupted in the process of transmission. Moreover, this encoding is robust, which means that if the inner products are evaluated with some noise, then the reconstructed version will be close to the original one with the error depending on the noise magnitude.
One of the most popular classes of frames in algorithmic applications is the set of random frames. Such frames became also the method of choice in compressed sensing where one needs to reconstruct a low complexity signal from a small number of linear measurements, see, e.g., [21]. For example, if complexity is measured as the size of the support, and the support itself is unknown, the random frames provide robust recovery with optimal or almost optimal theoretical guarantees.
To construct a random frame, consider a random vector X ∈ R n with centered uncorrelated coordinates of unit variance. In other words, assume that E X = 0 and E XX ⊤ = I n . Let vectors X 1 , . . . , X N be independent copies of X. The Law of Large Numbers implies that lim
and thus, with probability close to 1,
for all x ∈ R n provided that N = N (ε) is sufficiently large. Another, trivial way to construct a frame is to take several bases in R n and concatenate them. This allows an exact reconstruction of the transmitted signal if the number of corrupted coordinates is relatively small. Indeed, one can reconstruct the original vector from the set of transmitted coordinates for each basis separately and keep the copy which is repeated many times. While in practice the random frames perform better than such concatenated bases, it leads to a question whether a random frame contains a copy or copies of a nice basis. More precisely, a sequence of n vectors v 1 , . . . , v n ∈ R n is called a Riesz basis if it possesses the frame property (1.1). This property ensures that the reconstruction is robust, i.e., that the reconstructed vector is close to the original one if the coordinates are distorted by adding a small noise. These considerations lead to a natural question of determining the values of N for which a random frame {X 1 , . . . , X N } ⊂ R n contains one or many Riesz bases with high probability.
This problem can be conveniently translated to the language of random matrices. Namely, for an n × N matrix A, define its singular values as
where s j (A) = λ j (AA ⊤ ), and λ 1 (AA ⊤ ), . . . , λ n (AA ⊤ ) are eigenvalues of AA ⊤ arranged in the decreasing order. Also, define the condition number of A as
using the convention that κ(A) = ∞ whenever s min (A) = 0. With this notation, the frame property (1.1) can be rewritten as κ(A n,N ) ≤ C where A n,N is the n × N matrix with columns X 1 , . . . , X N . Thus, the problem of existence of a Riesz basis in a random frame can be recast as the question of existence of one or many well-conditioned square n × n submatrices of an n × N random matrix A n,N with i.i.d. entries. Our first main result shows that the probability of finding such a submatrix undergoes a phase transition when N is exponential in terms of n. Since the upper and the lower bound hold under somewhat different assumptions, we formulate them separately.
Denote by [N ] the set {1, . . . , N }. Let A be an n × N matrix. If I ⊂ [N ], denote by A I the submatix of A whose columns belong to I. The following theorem shows that if N is exponential in n, then with high probability, the n × N random matrix has many square submatrices with uniformly bounded condition numbers. In the language of frames, it means that a random frame with exponentially many vectors contains a large number of Riesz bases whose frame constants are uniformly bounded.
Theorem 1.1. Let A be an n×N matrix with i.i.d. symmetric non-degenerate entries. Then there exist constants c, C, α, β > 0 depending on the distribution of entries of A with the following property. Assume that N ≥ exp(Cn).
Then there exists L ≥ exp(cn)
The strategy of proving Theorem 1.1 relies on using a certain deterministic n × n matrix V having a bounded condition number. Denote by Col j (M ) the j-th column of the matrix M . We partition the set of integers [N ] into n subsets I 1 , . . . , I n of approximately the same size and show that with high probability, the set {Col i (A)} i∈I j contains many columns close to Col j (V ). Condition on the event that such columns exist and form an n × n matrix B taking one column from each set. Then conditionally this matrix can be viewed as a noisy version of the matrix V . This allows to show that with high probability, the matrix B has a bounded condition number as well.
The key to this strategy is a successful choice of the pattern matrix V . Since we strive to prove Theorem 1.1 under minimal assumptions, the choice of V becomes a non-trivial task. Indeed, the requirement that a column of A can be close to a column of V with a non-negligible probability forces us to look for matrices V whose entries are in the support of the distribution of an entry of A. The latter can be as small as two points, a and -a because of the symmetry assumption. Thus, we need to to construct V as a scaled copy of a matrix with ±1 entries. Such matrices are known in some cases. For instance, the condition number of any Hadamard matrix is one. An n × n matrix H is called Hadamard if n -1/2 H is an isometry. The earliest result on the existence of Hadamard matrices was probably proved by Sylvester [20] who showed that Hadamard matrices exist for dimension 2 k where k is any nonnegative integer (these matrices are now called Wash since their rows are Walsh functions). Hadamard matrices is a well-studied subject, and a number of constructions of such matrices are available, see e.g., the books [1], [12], and the references therein. In particular, Wallis [23] proved that if p > 3 is an integer, then there exists an Hadamard matrix of order 2 t p, where t = ⌊2log 2 (p -3)⌋. Craigen [7] improved Wallis's result by showing that for any odd number p, there exists an Hadamard matrix of order 2 t p, where t = 4 1 6 log 2 ((p -1)/2) + 2. Recently, de Launey [10] studied the asymptotic existence of Hadamard matrices and concluded that for any ϵ > 0, the set of odd numbers k for which there is a Hadamard matrix of order k2 2+[ϵlog 2 (k)] always has positive density in the set of natural numbers. Yet, the dimensions in which Hadamard matrices were constructed are rare.
This leads us to a task of constructing approximately Hadamard matrices, i.e., matrices with ±1 entries and bounded condition numbers. Some constructions of matrices with properties simlar to Hadamard's are available. For example, Banica, Nechita, and Życzkowski [2] defined an almost Hadamard matrix to be a N dimensional real square matrix H, such that H/ √ N is orthogonal, and is a local maximum of the ℓ 1 -norm of the entries on the orthogonal group O(N ). They showed the existence of almost Hadamard matrices under some special assumptions. There is also a notion of quasi-Hadamard matrix [2,15], which is defined as a square matrix with {-1, 1} entries that maximizes the absolute value of the determinant, but there are only very limited results on the existence of those matrices. In summary, no existing construction is directly related to our purpose.
The second main result of the paper is the following theorem asserting the existence of an approximately Hadamard matrix in all dimensions.
Theorem 1.2. There exist constants 0 < c < C such that for any n ∈ N, one can find an n × n matrix V with ±1 entries satisfying
The proof of Theorem 1.2 relies on Vinogradov's theorem from analytic number theory and combines number-theoretic and probabilistic ideas. The details are presented in Section 2. After Theorem 1.2 is proved, we prove Theorem 1.1 in Section 3.
The conclusion of Theorem 1.1 holds under minimal assumptions on the distribution of entries. If we assume that the entries of the matrix are subgaussian, then the bound of Theorem 1.1 becomes sharp. Recall that a random variable X is called subgaussian if there is a > 0 such that
If X is subgaussian then the smallest number a having this property is called the subgaussian norm of X and denoted ∥X∥ ψ 2 . Subgaussian random variables form a large family containing many naturally arising ones, see, e.g. [22].
The next theorem shows that finding a submatrix with a bounded condition number requires an exponential number of columns for matrices with subgaussian entries.
Theorem 1.3. Let X be a centered subgaussian random variable. Then there exist C, c, c, t 0 > 0 depending only on
with the following property. Let t > t 0 , and assume that N ≤ exp c t 4 n . Let A be an n × N matrix whose entries are independent copies of X. Then
We prove Theorem 1.3 in Section 4. Its proof is easier than that of Theorem 1.1 and relies on the Hanson-Wright inequality [19].
Acknowledgment. The second author is grateful to Marcin Bownik for helpful discussions and bringing his attention to the problem. Part of this work was done when the second author visited the Weizmann Institute of Science. He is grateful to the Institute for its hospitality. The authors thank a referee for thoroughly checking the manuscript and correcting many typos.
In this section we construct an n × n matrix with ±1 entries whose scaled copy acts on R n as an approximate isometry. More precisely, for any sufficiently large n, we construct an n × n matrix V such that its condition number κ(V ) is bounded by an absolute constant.
We use standard matrix norms below. Namely, ∥A∥ stands for the operator norm of an n × m matrix A = (a i,j ), and ∥A∥ HS stands for its Hilbert-Schmidt or Frobenius norm: We will apply an above mentioned result of Wallis [23] showing that Hadamard matrices exist in dimensions close to n 3 . Lemma 2.1. There is l 0 ∈ N such that for any l > l 0 , there exists an Hadamard matrix of dimension m(l) with m(l) = 2 2⌈log 2 (l-3)⌉ l.
We will need the following corollary.
Corollary 2.2. For any ε > 0, there exists N (ε) such that for any n > N 0 (ε), one can find an even number m ∈ [(1 -ε)n, (1 + ε)n] for which there exists an Hadamard matrix of size m × m.
Proof. For any n > 12, there exists a unique k
. By Lemma 2.1, there exists an Hadamard matrix of size m × m. Since
Since the tensor product of Hadamard matrices is an Hadamard matrix, and there are Hadamard matrices of sizes 2 × 2 and 4 × 4, there exist Hadamard matrices of sizes 2m(l) and 4m(l) for all l > l 0 . This allows completing the proof of the corollary in the remaining cases when 2 2k+1 (2
The aim of this section is to construct approximately Hadamard matrices in any dimension, i.e. matrices whose condition number is O(1). To this end, we use a construction of approximately Hadamard matrices of a prime size.
Let q ∈ N be an odd prime number. For k ∈ Z q , denote e q (k) = exp 2πi k q .
Define the Fourier transform on Z q setting v(j) = k∈Zq v(k)e q (jk) for a vector v ∈ C Zq and j ∈ Z q .
Lemma 2.3. Let q be an odd prime number. Then there exists a vector u q ∈ {-1, 1} Zq such that |û q (j)| -√ q ≤ √ qδ q for any j ∈ Z q with δ q = Cq -1/4 √ log q.
Proof. The construction closely follows the one in [14, Proposition 3.2], which in turn originates in [16,Theorem 9.2]. Let v : Z q → {-1, 1} be the Legendre symbol (quadratic character mod q). More precisely, let Q = {k ∈ Z q : k = j 2 (mod q) for some j ∈ Z q } \ {0} be the set of quadratic residues, and set
Then by a standard result on the Gauss sum, see e.g., [13, Proposition 6.3.2.; p.71], we have
The difference between v and the desired function u q is that v(0) = 0 and v(0) = 0. We will perturb v replacing some of its coordinates by -1 to change the value of v(0) as required while keeping the other Fourier coefficients close to their original values. To this end, consider a sequence of i.i.d. random variables {X k } k∈Q such that
Then u q : Z q → {-1, 1}, so we only have to check the values of the Fourier coefficients. Let us start with the expectations. We have
and
where the last equality follows if we fix k + l and sum over k -l first. Thus, |E ûq (j) -v(j)| ≤ 2 + q -1/2 for any j ∈ Z q \ {0}, and so | E ûq (j)| -√ q ≤ 3 for all j ∈ Z q .
The quantity ûq (j)-E ûq (j) is a linear combination of i.i.d. centered random variables X k -E X k , k ∈ Q with coefficients e q (jk) whose absolute value is bounded by 1. Therefore, Bernstein's inequality yields P (| ûq (j) -E ûq (j)| > t) ≤ 2 exp -c min(t 2 q -1/2 , t) for all t > 0 and j ∈ Z q . Setting t = Cq 1/4 √ log q and taking the union bound over j ∈ Z q , we obtain P | ûq (j) -E ûq (j)| ≤ Cq 1/4 log q for all j ∈ Z q ≥ 1 -q -1 > 0 if the constant C > 0 is chosen sufficiently large. The lemma follows. □ Corollary 2.4. Let q be an odd prime number. There exists a q × q matrix U q with ±1 entries such that √ q(1 -δ q ) ≤ s min (U q ) ≤ s max (U q ) ≤ √ q(1 + δ q )
with δ q = Cq -1/4 √ log q.
Proof. Represent Z q as {1, . . . , q}, and let u q : {1, . . . , q} → {-1, 1} be the vector defined in Lemma 2.3. Let U q be the circulant matrix with the first row u q . A circulant matrix is diagonal in the Fourier basis, see e.g., [9, Theorem 3.2.1; p. 72]. Therefore, the singular values of U q are the absolute values of its eigenvalues which are the Fourier coefficients of the generating vector u q . The result follows from Lemma 2.3. □ Remark 2.5. Corollary 2.4 implies that the matrix U q satisfies U q (U q ) ⊤ -qI q ≤ 3δ q q. (2.1) Inequality (2.1) will be used later in the proof of Theorem 1.2.
With this auxiliary construction in place, we can prove the main result of this section, namely Theorem 1.2.
Proof of Theorem 1.2. The proof of this theorem combines a deterministic construction of number-theoretic nature with a probabilistic argument. Without loss of generality, we can assume that n is larger than some number n 0 chosen in advance. Indeed, after the statement of the theorem is proved for n ≥ n 0 , we can adjust the constants c and C appropriately to make it hold for all n ∈ N.
We start with the case when n is even. Let ε > 0 be a number to be chosen later. A combination of the Prime Number Theorem and Vinogradov's sum of three primes theorem [18], yields that there exists N = N (ε) such that any even n > N has a decomposition (2.2)
where q 1 , . . . , q 4 are prime numbers. Indeed, by the Prime Number Theorem, there exists a prime number q 1 such that (1 -ε/2) n 4 ≤ q 1 ≤ (1 + ε/2) n 4 . Then m = n -q 1 is odd, and thus by a stronger version of Vinogradov's theorem, it can be decomposed as
and q 2 , q 3 , q 4 are primes. This immediately implies (2.2). Actually, decompositions with bounds tighter than (2.3) are available. More precisely, one can find a representations such as (2.3) with |q j -m/3| < m θ for some θ ∈ (0, 1), see e.g., [3,11,17]. However, the weaker version presented above will be sufficient for our purposes. Without loss of generality, assume that q 1 ≥ • • • ≥ q 4 =: q. We will consider the case q 3 > q 4 first. This is the most non-trivial case, and the other ones will be treated in the same way after obvious modifications. For j = {1, . . . , 4}, let U j be the matrix U q j constructed in Corollary 2.4, and denote by U top j the submatrix formed by the q top rows of U j . For j ∈ {1, 2, 3}, denote by U bottom j the submatrix of U j formed by its q j -q bottom rows. We will construct the matrix W = V ⊤ in the following block form:
where the matrix W top consists of the upper 4 block rows of W , and W bottom consists of the lower three. Here W j,k is a q × q k matrix if 1 ≤ j, k ≤ 4 and a (q j-4 -q) × q k matrix if j = 5, 6, 7, 1 ≤ k ≤ 4.
Let us define the matrices W j,k . The matrix W top will be deterministic, and the matrix W bottom will consist of deterministic and random blocks. For 1 ≤ j, k ≤ 4, set W j,k = ε j,k U top k , where ε j,k , j, k ∈ {1, . . . , 4} form a 4 × 4 Walsh matrix:
Now, let us define the matrices W j,k for j = 5, 6, 7. Set W j,j-4 = U bottom j-4 . For j = 5, 6, 7 and k ̸ = j -4, let W j,k be a random matrix with i.i.d. Rademacher entries.
Consider the (4q) × (4q) matrix W top (W top ) ⊤ first. The diagonal blocks of this matrix are close to nI q . More precisely, for any j ∈ {1, . . . , 4},
where the first inequality follows since
⊤ and the second one from (2.1).
Let us consider the off-diagonal blocks now. If i ̸ = j, i, j ∈ {1, . . . , 4} then similarly
where the first estimate follows from the triangle inequality, and the second one from
Combining the two inequalities, we obtain
for all sufficiently large n.
Let us introduce auxiliary (n -4q) × n matrices S and R defined by
In other words, R is the random part of the matrix W bottom , i.e., Recall that n -4q ≤ 4εn. In view of Corollary 2.4 and inequality (2.1),
Also,
Let R be an (n -4q) × n matrix with i.i.d. Rademacher entries. Then a simple symmetrization argument yields
which in combination with [19, Theorem 3.2] implies that
Another application of symmetrization yields
Fix a matrix R for which
at the same time. Let x ∈ S n-1 . Following the previous convention, we write
where x top ∈ R 4q and x bottom ∈ R n-4q . Assume first that x bottom 2 ≥ η, where the constant η > 0 will be chosen below. Then
Assume now that ∥x bottom ∥ 2 < η. Then ∥x top ∥ 2 > 1 -η, and (2.4) yields
Choosing the parameters ε and η sufficiently small, we can reconcile the two restrictions, i.e., select ε, η so the inequalities
(1 -2ε)η -C 1 √ ε > η/2 and C 2 η < 1 4 hold at the same time. With this choice, the previous argument shows that
√ n for all x ∈ S n-1 , which means that
Obtaining a bound for s max (W ) is easier. Inequalities (2.4) and (2.5) imply
This in combination with (2.6) yields
which proves the theorem in the case q 3 > q.
If q j = q for some j ∈ {1, 2, 3}, then we repeat the same argument with the block rows of W containing q j -q = 0 rows removed. For instance, if q 1 > q and q 2 = q 3 = q, then we consider the n × n matrix W with W top being the same as in the previous case and W bottom = (W 5,1 • • • W 5,4 ) which is a (q 1 -q) × n matrix.
This completes the proof of the theorem in the case when n is even.
Assume that n is odd. By Corollary 2.2, if n is sufficiently large, then we can find an even number
n 4 for which there exists an Hadamard matrix V of size m × m. Note that n -m is odd and
so using Vinogradov's theorem again, we obtain a decomposition n -m = q 1 + q 2 + q 3 , where q 1 , q 2 , q 3 are prime numbers and 1-ε 4 n ≤ q j ≤ 1+ε 4 n. At this point we can apply the same argument we used in the case of an even n with one of the matrices U 1 , . . . , U 4 replaced by V . This completes the proof of the theorem. □
In this section we prove Theorem 1.1. As was explained in the Introduction, the proof relies on finding columns of A which are close to columns of a scaled copy of the V constructed in the previous section. Conditioned on the event that such selection is possible, we prove that with high probability, the constructed submatrix has a bounded condition number. We start with the latter task, namely with analyzing a random matrix close to V . Lemma 3.1. Let V be an n × n matrix with ±1 entries such that
There exists δ ∈ (0, 1) for which any n × n matrix Y with i.i.d. entries Y i,j such that E Y i,j = 0 and |Y i,j | ≤ δ a.s. satisfies
Proof. The proof of Lemma 3.1 uses the basic net argument, see e.g., [22]. Since Y has i.i.d. centered subgaussian entries with ∥Y i,j ∥ ψ 2 ≤ ∥Y i,j ∥ ∞ ≤ δ,
Therefore,
as we can always assume that C 3.1 ≥ 1 and choose δ sufficiently small. Similarly,
where as before, the last inequality holds for any sufficiently small δ. The result follows by combining the two bounds above. □
We now proceed to proving the main result, Theorem 1.1.
Proof ot Theorem 1.1. Since the distribution of entries of A is non-degenerate, there exists a > 0 such that for any ν > 0
By the symmetry of distribution, we also have the same property for -a in place of a.
Let δ > 0 be as in Lemma 3.1, and denote ν = a 4 δ. Let Z be a random variable having the same distribution as a i,j conditioned on the event that |a i,j -a| ≤ ν. More precisely, for a Borel set E ⊂ R, set
Then R is a centered random variable such that
Let C > 0 be a constant to be chosen later, and assume that N ≥ exp(2Cn). Partition [N ] into a union of sets I 1 , . . . , I n such that
Let V be the n×n matrix with ±1 entries constructed in Theorem 1.2. Denote its columns by V 1 , . . . , V n and the columns of A by A 1 , . . . , A N . Let M be a number to be chosen later. Let E be the event that for any j ∈ [n], there exist at least M numbers k ∈ I j with
If E occurs, denote by k(j, 1), . . . , k(j, M ) the first M numbers k ∈ I j having this property. Then conditioned on E, for any m ∈ [M ], the matrix A E,m with columns A k(1,m) , . . . , A k(n,m) has the same distribution as E Z • (V + Y ), where Y is an n × n random matrix whose entries have the form Y i,j = V i,j R i,j , where R i,j are independent copies of R. In view of Lemma 3.1, this implies that for any m ∈ [M ],
Since conditionally on E, the matrices A E,1 , . . . , A E,M are independent, Bernstein's inequality allows to conclude that
To complete the proof, we have to show that the probability of E c is small. To this end, denote η = P(|a i,j -a| ≤ ν). Then by the symmetry of distribution of the entries of A,
where the last inequality holds if C = C(η) is chosen sufficiently large. Note that the events ∥A k -aV j ∥ ∞ ≤ ν are independent for all k ∈ I j . At this point, Bernstein's inequality yields
Therefore,
Let L = M/2, and α = 4 C 3.1 c 3.1 . Combining the previous inequalities, we obtain that
for an appropriate β > 0. This completes the proof of the theorem. □
No submatrices with a small condition number
In this section, we prove Theorem 1.3.
Proof. Without loss of generality, we can assume that ∥X∥ 2 = (E X 2 ) 1/2 = 1. Throughout the proof, we denote by C, c, c ′ , etc. constants depending only on ∥X∥ ψ 2 . Consider an n × n random matrix B whose entries are independent copies of X. We claim that