Need help bounding the $L^2$ induced operator norm by the maximum $L^2$ norm of the columns.

36 Views Asked by At

I need to bound the following operator for some matrix $X \in \mathbb{R}^{N_0\times m}$: \begin{equation} \Gamma(X) = \sup_{T \subset [N_0], \lvert T \rvert = m } \lVert X^\top_T \rVert \end{equation} where $X^\top_T$ denotes $X^\top$ with all columns not indexed by $T$ set to zero and the norm is the spectral norm. The bound now given is \begin{equation} \Gamma(X) \leq \sqrt{m} \max_{1 \leq j \leq N_0} \lVert X_j \rVert_2 \end{equation} where $X_j$ denotes the rows of $X$.

I think I can bound $\Gamma(X)$ using Gershgorin's disc theorem by the $\lVert X_j \rVert_1$ norm but I do not immediately see an idea for this bound. Thanks for the help in advance!

Edit: I think I found the answer. In general if we assume we just have a matrix $A \in \mathbb{R}^{m \times m}$, then \begin{align} \lVert A \rVert_2^2 &= \sup_{\lVert x \rVert_2 = 1} \lVert Ax \rVert_2^2 = \sup_{\lVert x \rVert_2 = 1} \sum_{i=1}^m \langle a_i, x \rangle \\ &\leq \sup_{\lVert x \rVert_2 = 1} \sum_{i=1}^m \lVert a_i \rVert_2^2\lVert x \rVert_2^2 \leq m \max_{1 \leq i \leq m} \lVert a_i \rVert_2^2. \end{align} where we just use the Cauchy Schwartz inequality once. Taking the squareroot yields the claim.