I'm trying to characterize the $(\infty,1)$-operator norm of a particular matrix. I'm aware that it is NP-hard to calculate the norm in general, but I'm only interested in a bound in a particular setting, which might be tractable.
Let $\mathbf{x}_i \in \mathbb{R}^m$ for $i \in [n] = \{1, \dotsc, n\}$ and let $\mathbf{y} \in \mathbb{R}^m$. We know that $n > m$. We also know that $\mathbf{x}_i^T \mathbf{x}_i \leq 1$ for all $i \in [n]$ and $\mathbf{y}^T \mathbf{y} \leq 1$. Stack $\mathbf{x}_i$ into $n$-by-$m$ matrix $\mathbf{X} = [\mathbf{x}_1, \dotsc, \mathbf{x}_n]^T$. For some $\phi > 0$, define $\mathbf{A} = (\mathbf{X} \mathbf{X}^T + \phi \mathbf{I})^{-1}$ and $\mathbf{b} = \mathbf{X} \mathbf{y}$.
I'm interested in an upper bound on $\lVert \mathbf{A} \mathbf{b} \rVert_1$. The approach I'm taking is to use the $(\infty,1)$-operator norm: $\lVert \mathbf{A} \mathbf{b} \rVert_1 \leq \lVert \mathbf{A} \rVert_{\infty,1} \lVert \mathbf{b} \rVert_{\infty}$, where $$ \lVert \mathbf{A} \rVert_{\infty,1} = \sup_{\mathbf{v} : \lVert \mathbf{v} \rVert_{\infty}=1} \lVert \mathbf{A} \mathbf{v} \rVert_1 \qquad\qquad \lVert \mathbf{b} \rVert_{\infty} = \max_{i\in[n]} \mathbf{x}_i^T \mathbf{y}. $$ This is useful because the Cauchy-Schwarz inequality gives $\mathbf{x}_i^T \mathbf{y} \leq 1$ for all $i\in[n]$, so $\lVert \mathbf{b} \rVert_{\infty} \leq 1$.
My question: Is there some way to bound $\lVert \mathbf{A} \rVert_{\infty,1}$ in terms of $\phi$ in this setting?
Any ideas or suggestions would be greatly appreciated. Thanks!
(Note that this is possible for the $(2,2)$-operator norm, because then $\lVert \mathbf{A} \rVert_{2,2} \leq 1 / \lambda_{\min}$ where $\lambda_{\min}$ is the smallest eigenvalue of $\mathbf{X} \mathbf{X}^T + \phi \mathbf{I}$, which we know is lower bounded by $\phi$.)
We have the bound $\lVert \mathbf{A} \rVert_{\infty,1} \leq \phi^{-1} n$ (see below). But maybe we can do better?
Let $\mathbf{C} = \phi \mathbf{A} = (\phi^{-1} \mathbf{X} \mathbf{X}^T + \mathbf{I})^{-1}$, meaning that $\lVert \mathbf{A} \rVert_{\infty,1} = \phi^{-1} \lVert \mathbf{C} \rVert_{\infty,1}$. Using (the simpler version of) the Woodbury matrix identity, we have $$ \mathbf{C} = \mathbf{I} - \phi^{-1} \mathbf{X} (\mathbf{I} + \phi^{-1} \mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T. $$ Let $\mathbf{L}$ be the Cholesky decomposition of $(\mathbf{I} + \phi^{-1} \mathbf{X}^T\mathbf{X})^{-1}$, so that $\mathbf{L}\mathbf{L}^T = (\mathbf{I} + \phi^{-1} \mathbf{X}^T\mathbf{X})^{-1}$. Furthermore, let $\mathbf{D} = \phi^{-1/2} \mathbf{L}^T \mathbf{X}^T$, so $\mathbf{C} = \mathbf{I} - \mathbf{D}^T\mathbf{D}$. Because $\mathbf{D}^T\mathbf{D}$ is a Gram matrix, it is positive semidefinite.
By Rohn (2000), we have $$ \lVert \mathbf{C} \rVert_{\infty,1} = \max_{\mathbf{z} \in \{\pm1\}^n} \mathbf{z}^T \mathbf{C} \mathbf{z}. $$ Note that $\mathbf{z}^T \mathbf{I} \mathbf{z} = n$ for all $\mathbf{z} \in \{\pm1\}^n$, so $$ \lVert \mathbf{C} \rVert_{\infty,1} = n - \min_{\mathbf{z} \in \{\pm1\}^n} \mathbf{z}^T \mathbf{D}^T\mathbf{D} \mathbf{z}. $$ By positive semidefiniteness, $\mathbf{z}^T \mathbf{D}^T\mathbf{D} \mathbf{z} \geq 0$ for all $\mathbf{z} \in \{\pm1\}^n$.