Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness

Shravas Rao ¹¹1Funding: This material is based upon work supported by the National Science Foundation under Award No. 2348489 Department of Computer Science, Portland State University
1900 SW 4th Ave, Portland, OR 97201
[email protected]

Abstract

A matrix $\Phi\in\mathbb{R}^{Q\times N}$ satisfies the restricted isometry property if $\|\Phi x\|_{2}^{2}$ is approximately equal to $\|x\|_{2}^{2}$ for all $k$ -sparse vectors $x$ . We give a construction of RIP matrices with the optimal $Q=O(k\log(N/k))$ rows using $O(k\log(N/k)\log(k))$ bits of randomness. The main technical ingredient is an extension of the Hanson-Wright inequality to $\varepsilon$ -biased distributions.

Keywords: Compressed Sensing, Randomness Reduction, Restricted Isometry Property

1 Introduction

A matrix $\Phi\in\mathbb{R}^{Q\times N}$ is said to satisfy the $(k,\eta)$ -restricted isometry property if for every $k$ -sparse vector $x\in\mathbb{R}^{N}$ , one has

(1-\eta)\|x\|_{2}^{2}\leqslant\|\Phi x\|_{2}^{2}\leqslant(1+\eta)\|x\|_{2}^{2}.

where $\|\cdot\|_{2}$ denotes the $\ell_{2}$ norm. This notion, introduced by Candès and Tao [CT05], has many applications especially in the field of compressed sensing [Can08].

A major goal is to construct such matrices so that the number of rows $Q$ is as small as possible compared to $k$ and $N$ . In this note, we will mostly ignore the dependence on $\eta$ . It is known that $Q=\Omega(k\log(N/k))$ rows are necessary for the restricted isometry property to hold [FPRU10].

If the construction is required to be deterministic there are many constructions with $Q=\widetilde{O}(k^{2})$ rows [Kas75, AGHP92, DeV07, NT11]. In a breakthrough result due to Bourgain, Dilworth, Ford, Konyagin, and Kutzarova [BDF⁺11], a construction with $O(k^{2-\varepsilon_{0}})$ rows was obtained, for some very small constant $\varepsilon_{0}$ . This was later improved by Mixon [Mix15], and Bandeira, Mixon, and Moreira [BMM17] conditioned on a number-theoretic conjecture. It is known that significant improvements would imply explicit constructions of Ramsey graphs [Gam20].

On the other hand, there exist randomized constructions that do achieve the optimal number of rows. In particular, if each entry is an independent Gaussian or Bernoulli random variable, then the restricted isometry property holds for $Q=O(k\log(N/k))$ [CT06, BDDW08, MPTJ08].

Randomized constructions can be evaluated by the number of bits of randomness they use. When all entries are independent, then $O(NQ)$ bits of randomness are needed. Thus, towards the goal of deterministic constructions of matrices that satisfy the restricted isometry property, one can ask if there exist constructions that use fewer bits of randomness.

There is a long line of work that considers a construction where each row of $\Phi$ is a random row of a Fourier or Walsh-Hadamard matrix [CT06, RV08, CGV13, Bou14, HR17]. Such constructions use $O(Q\log(N))$ bits of randomness. The analysis due to Haviv and Regev [HR17], and later improved by [BDJR21], obtain the best-known bound on the number of rows $Q=O(k\log(N)\log^{2}(k))$ . However, it is known that when the rows are obtained from a Walsh-Hadamard matrix, the number of rows must be $Q=\Omega(k\log(N)\log(k))$ [BLL⁺23]. Thus, such constructions can not achieve the optimal number of rows that constructions with independent entries can.

Another choice of construction allows for the entries of $\Phi$ to come from a $O(Q)$ -wise independent distribution. Combining the analysis of [CW09] with [BDDW08], a slight modification to the analysis for independent entries holds for $O(Q)$ -wise independent entries. In particular, one can let $Q$ be the optimal $O(k\log(N/k))$ . Standard constructions of $O(Q)$ -wise independent random variables when $Q=O(k\log(N/k))$ require $O(k\log(N/k)\log(N))$ bits of randomness. This was slightly improved in [KN10] to a construction that requires only $O(k\log(N/k)\log(k\log(N/k)))$ bits of randomness.

Finally, a third line of work uses pseudorandom properties of the Legendre symbol. This approach uses $O(k\log(N)\log(k))$ bits of randomness, but requires $Q=O(k\log(N)\log^{2}(k))$ rows [BFMM16].

In this note, we use almost $O(Q)$ -wise independent distributions when $Q=O(k\log(N/k))$ to show that that $O(k\log(N/k)\log(k))$ random bits is enough to construct a matrix that satisfies the restricted isometry property. This is the least amount of randomness used among all randomized constructions with the optimal number of rows listed above. However, when $k\sim N^{c}$ for some constant $c$ for example, this recovers the result in [KN10] as $\log(k)=\Theta(\log(N))$ in this case.

The pseudorandom properties of the almost $O(Q)$ -wise independent distributions that we use are similar to the pseudorandom properties of the Legendre symbol used in [BFMM16]. Compared to [KN10] and [BFMM16], our proof is arguably simpler. However, it is conjectured that the Legendre symbol can be used to construct deterministic RIP matrices, something that is not true for the techniques in this note.

Theorem 1.1.

There exists a distribution of $Q\times N$ matrices for $Q=O(k\log(N/k)\eta^{-2})$ that can be sampled efficiently using $O(k\log(k)\log(N/k))$ bits of randomness such that a sample $\Phi$ from this distribution satisfies the $(k,\eta)$ -restricted isometry property with high probability.

The proof of this theorem follows the same structure as [CW09] with [BDDW08] when the entries of $\Phi$ come from a truly $O(Q)$ -wise independent distribution. In particular, one focuses on the more general question of constructing a matrix $\Phi$ that is a Johnson-Lindenstrauss projection. That is, one shows that for any fixed unit vector $x$

\Pr\left[\left|\|\Phi x\|_{2}^{2}-1\right|\geqslant\eta\right]\leqslant\exp(-cQ\eta^{2})

(1)

for some constant $c$ . It was shown in [BDDW08] that if Eq. (1) holds for $Q=O(k\log(N/k))$ when $\eta<1$ , then the random matrix $\Phi$ satisfies the restricted isometry property with high probability.

In this note, we only consider the case of when $x$ is $k$ -sparse. That is, when $x$ is not $k$ -sparse, and the entries of $\Phi$ come from an almost $O(Q)$ -wise independent distribution, the number of random bits required for our generalization of the Hanson-Wright inequality to hold is too large to improve upon the result in [CW09]. However, for the purposes of constructing a matrix that satisfies the restricted isometry property, it is enough to consider only $k$ -sparse $x$ . This is because for the restricted isometry property to hold, it is enough to show that $\|\phi x\|_{2}^{2}\approx\|x\|_{2}^{2}$ for $k$ -sparse vectors $x$ .

2 Preliminaries

If $x\in\mathbb{R}^{N}$ is a vector, we define the norm

\|x\|_{p}^{p}=\sum_{i=1}^{N}|x(i)|^{p}.

If $A\in\mathbb{R}^{N\times N}$ is a matrix, we define the norms

\|A\|_{L_{1}}=\sum_{i,j}|A_{i,j}|,\;\;\|A\|_{2}=\max_{\|x\|_{2}=1}\|Ax\|_{2},\;\;\|A\|_{S_{2}}=(\operatorname{tr}(AA^{*}))^{1/2}.

The construction of matrices is derived from $\varepsilon$ -biased distributions, which we define below.

Definition 2.1.

A distribution $S\subseteq\{-1,1\}^{n}$ is $\varepsilon$ -biased $\ell$ -wise independent if when $x=(x_{1},x_{2},\ldots,x_{n})$ is sampled uniformly from $S$ , for all $y\subseteq[n]$ such that $0<|y|\leqslant\ell$ ,

\left|\mathbb{E}\left[\prod_{i\in y}x_{i}\right]\right|\leqslant\varepsilon.

There exist $\varepsilon$ -biased $\ell$ -wise independent distributions $S$ such that $\log(|S|)=O(\log(\log(n))+\ell+\log(1/\varepsilon))$ , due to [AGHP92, NN93].

The main ingredient of the proof of Theorem 1.1 is a generalization of the Hanson-Wright inequality. This inequality can often be used to obtain concentration inequalities for quadratic forms using Markov’s inequality, as will be done here. We state the original below [HW71] (see Theorem 3.1 in [KN14]).

Theorem 2.2.

There exists a constant $C$ such that the following holds. Let $(z_{1},\ldots,z_{n})$ be independent random variables uniform over $\{-1,1\}$ . Then for any symmetric $B\in\mathbb{R}^{n\times n}$ and integer $\ell\geqslant 2$ a power of $2$ ,

\mathbb{E}\left[\left(z^{T}Bz-\operatorname{tr}(B)\right)^{\ell}\right]\leqslant C^{\ell}\max\left\{\sqrt{\ell}\cdot\|B\|_{S_{2}},\ell\cdot\|B\|_{2}\right\}^{\ell}

3 Proof of the Main Theorem

The main technical ingredient of this note is a generalization of the Hanson-Wright inequality [HW71] for $\varepsilon$ -biased distributions which we state and prove below.

Lemma 3.1.

There exists a constant $C$ such that the following holds. Let $(z_{1},\ldots,z_{n})$ be a sample from an $\varepsilon$ -biased $2\ell$ -wise independent distribution from $\{1,-1\}^{n}$ for any integer $\ell\geqslant 2$ a power of $2$ . Then for any symmetric $B\in\mathbb{R}^{n\times n}$ ,

\mathbb{E}\left[\left(z^{T}Bz-\operatorname{tr}(B)\right)^{\ell}\right]\leqslant\varepsilon\|B\|_{L_{1}}^{\ell}+C^{\ell}\max\left\{\sqrt{\ell}\cdot\|B\|_{S_{2}},\ell\cdot\|B\|_{2}\right\}^{\ell}

Proof.

Let $\mathcal{S}=\{(i,j)\mid i,j\in[n],i\neq j\}$ . Then,

(z^{T}Bz-\operatorname{tr}(B))^{\ell}=\sum_{s\in\mathcal{S}^{\ell}}\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}B_{s_{k,1},s_{k,2}}.

(2)

Let $\mathcal{S}^{\prime}$ be the set of sequences in $\mathcal{S}^{\ell}$ such that each $i\in[n]$ appears in an even number of pairs. Then Eq. (2) can be rewritten as

$\displaystyle\left(\sum_{s\in\mathcal{S}^{\ell}\backslash\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}B_{s_{k,1},s_{k,2}}\right)$	$\displaystyle+\left(\sum_{s\in\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}B_{s_{k,1},s_{k,2}}\right)$
	$\displaystyle=\left(\sum_{s\in\mathcal{S}^{\ell}\backslash\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}B_{s_{k,1},s_{k,2}}\right)+\left(\sum_{s\in\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}B_{s_{k,1},s_{k,2}}\right)$	(3)
	$\displaystyle\leqslant\left(\sum_{s\in\mathcal{S}^{\ell}\backslash\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}B_{s_{k,1},s_{k,2}}\right)+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}.$

The equality follows from the definition of $\mathcal{S}$ and the fact that $z_{i}^{2}=1$ for all $i$ . The inequality follows from the fact that when the $z_{i}$ are independent, the first sum in Eq. (3) evaluates to $0$ , and thus, Theorem 2.2 can be used to bound the second sum.

Because the $z_{i}$ come from an $\varepsilon$ -biased $2\ell$ -wise independent distribution,

\left|\prod_{k=1}^{\ell}z_{s_{k,1}}z_{s_{k,2}}\right|\leqslant\varepsilon

when $s\not\in\mathcal{S}^{\prime}$ . Thus, the left-hand side of Eq. (3) is bounded above by

	$\displaystyle\varepsilon\left(\sum_{s\in\mathcal{S}^{\ell}\backslash\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}\left\|B_{s_{k,1},s_{k,2}}\right\|\right)$	$\displaystyle+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$
		$\displaystyle\leqslant\varepsilon\left(\sum_{s\in\mathcal{S}^{\ell}}\prod_{k=1}^{\ell}\left\|B_{s_{k,1},s_{k,2}}\right\|\right)+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$
		$\displaystyle=\varepsilon\\|B\\|_{L_{1}}^{\ell}+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$

as desired. ∎

We now prove Theorem 1.1 using the same main ideas as in [KN10, Theorem 6].

Proof of Theorem 1.1.

We let $\Phi$ come from a $(k^{2}\ell/Q)^{-\ell/2}$ -biased $\ell$ -wise independent distribution for $\ell=O(Q\eta^{2})=O(k\log(N/k))$ , normalized so that all entries are from the set $\{-1/Q,1/Q\}$ . There exists a construction using the desired number of random bits, $O(\ell\log(k))=O(k\log(k)\log(N/k))$ , due to [AGHP92, NN93].

By Theorem 5.2 in [BDDW08], it is enough to show that Eq. (1) holds when $x$ is a $k$ -sparse vector such that $\|x\|_{2}=1$ , and $\eta<1$ .

For every $k$ -sparse vector $x$ , let $B_{x}$ be a $QN\times QN$ block-diagonal matrix with $Q$ blocks, where each block is equal to $xx^{T}/Q$ . Let $z\in\mathbb{R}^{QN}$ contain each row of $\Phi$ stacked in a vector. Note that $B_{x}$ contains at most $k^{2}Q$ non-zero entries as $x$ is $k$ -sparse, and thus $\|B_{x}\|_{L_{1}}\leqslant kQ^{1/2}\|B_{x}\|_{S_{2}}$ . By Lemma 3.1, for some constants $C_{1}$ and $C_{2}$ ,

	$\displaystyle\mathbb{E}\left[\left(z^{T}B_{x}z-\operatorname{tr}(B_{x})\right)^{\ell}\right]$	$\displaystyle\leqslant\ell^{\ell/2}\\|B_{x}\\|_{S_{2}}^{\ell}+C_{1}^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B_{x}\\|_{S_{2}},\ell\cdot\\|B_{x}\\|_{2}\right\}^{\ell}$
		$\displaystyle\leqslant C_{2}^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B_{x}\\|_{S_{2}},\ell\cdot\\|B_{x}\\|_{2}\right\}^{\ell}$

By direct computation, $z^{T}B_{x}z=\|\Phi x\|_{2}^{2}$ , $\operatorname{tr}(B_{x})=1$ , $\|B_{x}\|_{S_{2}}^{2}=Q\|x/Q\|_{2}^{4}=1/Q$ and $\|B_{x}\|_{2}=\|x^{T}x/Q\|_{2}=1/Q$ . Thus, the bound becomes

\mathbb{E}\left[\left(\left\|\Phi x\right\|_{2}^{2}-1\right)^{\ell}\right]\leqslant C_{2}^{\ell}\max\left\{\sqrt{\ell/Q},\ell/Q\right\}^{\ell}.

By Markov’s inequality, one has

	$\displaystyle\Pr\left[\left(\left\\|\Phi x\right\\|_{2}^{2}-1\right)^{2}\geqslant\eta^{2}\right]$	$\displaystyle=\Pr\left[\left(\left\\|\Phi x\right\\|_{2}^{2}-1\right)^{\ell}\geqslant\eta^{\ell}\right]$
		$\displaystyle\leqslant C_{2}^{\ell}\eta^{-\ell}\max\left\{\sqrt{\ell/Q},(\ell/Q)\right\}^{\ell}$
		$\displaystyle\leqslant\exp(-cQ\eta^{2})$

for some constant $c$ and $\ell=O(Q\eta^{2})$ , where the last inequality follows by noting that $\eta<1$ . ∎

References

[AGHP92] N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple constructions of almost $k$ -wise independent random variables. Random Structures Algorithms, 3(3):289–304, 1992. ISSN 1042-9832,1098-2418. doi:10.1002/rsa.3240030308.
[BDDW08] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin. A simple proof of the restricted isometry property for random matrices. Constr. Approx., 28(3):253–263, 2008. ISSN 0176-4276,1432-0940. doi:10.1007/s00365-007-9003-x.
[BDF⁺11] J. Bourgain, S. Dilworth, K. Ford, S. Konyagin, and D. Kutzarova. Explicit constructions of RIP matrices and related problems. Duke Math. J., 159(1):145–185, 2011. ISSN 0012-7094,1547-7398. doi:10.1215/00127094-1384809.
[BDJR21] S. Brugiapaglia, S. Dirksen, H. C. Jung, and H. Rauhut. Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Appl. Comput. Harmon. Anal., 53:231–269, 2021. ISSN 1063-5203,1096-603X. doi:10.1016/j.acha.2021.01.004.
[BFMM16] A. S. Bandeira, M. Fickus, D. G. Mixon, and J. Moreira. Derandomizing restricted isometries via the Legendre symbol. Constr. Approx., 43(3):409–424, 2016. ISSN 0176-4276,1432-0940. doi:10.1007/s00365-015-9310-6.
[BLL⁺23] J. Blasiok, P. Lopatto, K. Luh, J. Marcinek, and S. Rao. An improved lower bound for sparse reconstruction from subsampled Walsh matrices. Discrete Anal., pages Paper No. 3, 9, 2023. ISSN 2397-3129.
[BMM17] A. S. Bandeira, D. G. Mixon, and J. Moreira. A conditional construction of restricted isometries. Int. Math. Res. Not. IMRN, (2):372–381, 2017. ISSN 1073-7928,1687-0247. doi:10.1093/imrn/rnv385.
[Bou14] J. Bourgain. An improved estimate in the restricted isometry problem. In Geometric aspects of functional analysis, volume 2116 of Lecture Notes in Math., pages 65–70. Springer, Cham, 2014. doi:10.1007/978-3-319-09477-9˙5.
[Can08] E. J. Candès. The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris, 346(9-10):589–592, 2008. ISSN 1631-073X. doi:10.1016/j.crma.2008.03.014.
[CGV13] M. Cheraghchi, V. Guruswami, and A. Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM J. Comput., 42(5):1888–1914, 2013. ISSN 0097-5397. doi:10.1137/120896773.
[CT05] E. J. Candes and T. Tao. Decoding by linear programming. IEEE Trans. Inform. Theory, 51(12):4203–4215, 2005. ISSN 0018-9448. doi:10.1109/TIT.2005.858979.
[CT06] E. J. Candes and T. Tao. Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory, 52(12):5406–5425, 2006. ISSN 0018-9448. doi:10.1109/TIT.2006.885507.
[CW09] K. L. Clarkson and D. P. Woodruff. Numerical linear algebra in the streaming model. In M. Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 205–214. ACM, 2009. doi:10.1145/1536414.1536445.
[DeV07] R. A. DeVore. Deterministic constructions of compressed sensing matrices. J. Complexity, 23(4-6):918–925, 2007. ISSN 0885-064X,1090-2708. doi:10.1016/j.jco.2007.04.002.
[FPRU10] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. The Gelfand widths of $\ell_{p}$ -balls for $0<p\leqslant 1$ . J. Complexity, 26(6):629–640, 2010. ISSN 0885-064X. doi:10.1016/j.jco.2010.04.004.
[Gam20] D. Gamarnik. Explicit construction of RIP matrices is Ramsey-hard. Comm. Pure Appl. Math., 73(9):2043–2048, 2020. ISSN 0010-3640,1097-0312. doi:10.1109/tit.2014.2331341.
[HR17] I. Haviv and O. Regev. The restricted isometry property of subsampled Fourier matrices. In Geometric aspects of functional analysis, volume 2169 of Lecture Notes in Math., pages 163–179. Springer, Cham, 2017.
[HW71] D. L. Hanson and F. T. Wright. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist., 42:1079–1083, 1971. ISSN 0003-4851. doi:10.1214/aoms/1177693335.
[Kas75] B. S. Kashin. The diameters of octahedra. Uspehi Mat. Nauk, 30(4(184)):251–252, 1975. ISSN 0042-1316.
[KN10] D. M. Kane and J. Nelson. A derandomized sparse Johnson-Lindenstrauss transform. arXiv:1006.3585, 2010.
[KN14] D. M. Kane and J. Nelson. Sparser Johnson-Lindenstrauss transforms. J. ACM, 61(1):Art. 4, 23, 2014. ISSN 0004-5411,1557-735X. doi:10.1145/2559902.
[Mix15] D. G. Mixon. Explicit matrices with the restricted isometry property: breaking the square-root bottleneck. In Compressed sensing and its applications, Appl. Numer. Harmon. Anal., pages 389–417. Birkhäuser/Springer, Cham, 2015. ISBN 978-3-319-16041-2; 978-3-319-16042-9.
[MPTJ08] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann. Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constr. Approx., 28(3):277–289, 2008. ISSN 0176-4276. doi:10.1007/s00365-007-9005-8.
[NN93] J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. ISSN 0097-5397. doi:10.1137/0222053.
[NT11] J. L. Nelson and V. N. Temlyakov. On the size of incoherent systems. J. Approx. Theory, 163(9):1238–1245, 2011. ISSN 0021-9045,1096-0430. doi:10.1016/j.jat.2011.04.001.
[RV08] M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math., 61(8):1025–1045, 2008. ISSN 0010-3640. doi:10.1002/cpa.20227.

	$\displaystyle\varepsilon\left(\sum_{s\in\mathcal{S}^{\ell}\backslash\mathcal{S}^{\prime}}\prod_{k=1}^{\ell}\left\|B_{s_{k,1},s_{k,2}}\right\|\right)$	$\displaystyle+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$
		$\displaystyle\leqslant\varepsilon\left(\sum_{s\in\mathcal{S}^{\ell}}\prod_{k=1}^{\ell}\left\|B_{s_{k,1},s_{k,2}}\right\|\right)+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$
		$\displaystyle=\varepsilon\\|B\\|_{L_{1}}^{\ell}+C^{\ell}\max\left\{\sqrt{\ell}\cdot\\|B\\|_{S_{2}},\ell\cdot\\|B\\|_{2}\right\}^{\ell}$