# Minimization version of matrix p-norms?

I considered a minimization version of matrix p-norms, defined for a matrix $$A$$ by

$$f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.$$

Notice that $$f_p(A) = 0$$ if and only if $$A$$'s columns are linearly dependent. Therefore $$f_p(A)$$ can be seen as a measure of the linear independence of $$A$$'s columns: the larger $$f_p(A)$$ is, the more independent $$A$$'s columns are.

When $$p=2$$, $$f_2(A)$$ equals the smallest singular value of $$A$$ and can be computed by doing SVD. When $$p\neq 2$$, is there any known algorithm than can compute $$f_p(A)$$? Or if this problem has not been studied before for the $$p\neq 2$$ case, is it likely to be of interest?

• An equivalent formulation is to minimize $||Ap||_p$ over the unit ball of $\ell_p$. Minimizing a convex function over a convex set is almost a convex program -- I think you need the feasible set to be defined by linear constraints. Still, I suspect that some version of guarded Newton's method should work. – Aryeh Oct 28 '18 at 15:58
• If $A$ is invertible, then this is equal to $1/\|A^{-1}\|_{p \to p}$. So this is the same as computing $\ell_p\to \ell_p$ operator norms. @Aryeh this problem is equivalent to minimizing $\|Ax\|_p$ over the unit sphere of $\ell_p$, which is not a convex set. – Sasho Nikolov Oct 29 '18 at 3:22
• Oh right— the sphere, not the ball! – Aryeh Oct 29 '18 at 5:02
• @SashoNikolov What if A is rectangular, and is full column rank but not full row rank? Is it still solvable by computing $\ell_p \to \ell_p$ norm? – Octopus Oct 29 '18 at 12:14

Suppose that $$A$$ is an $$m\times n$$ matrix, and let $$\mathcal{A}$$ be the corresponding linear operator whose matrix (w.r.t. the standard basis) is $$A$$. Let $$W\subseteq \mathbb{R}^m$$ be the span of the columns of $$A$$, or, equivalently, the range of $$\cal A$$. I am going to treat $$\mathcal{A}$$ as an operator from $$\mathbb{R}^n$$ to $$W$$. As long as $$A$$ has full column rank, the operator $$\mathcal{A}$$ is an injection, so it is invertible on its range: let $$\mathcal{A}^{-1}:W \to \mathbb{R}^n$$ be its inverse.
You are asking about the quantity $$\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p} = \min_{y \in W\setminus \{0\}}\frac{\|y\|_p}{\|\mathcal{A}^{-1}y\|_p} = \left(\max_{y \in W\setminus \{0\}}\frac{\|\mathcal{A}^{-1}\|_p}{\|y\|_p}\right)^{-1}$$
So, your quantity $$f_p(A)$$ is the operator norm of $$\mathcal{A}^{-1}$$, taken as an operator from the normed space $$(W, \|\cdot\|_p)$$ to $$(\mathbb{R}^n, \|\cdot\|_p)$$. In the special case when $$A$$ is square, this is just an $$\ell_p \to \ell_p$$ operator norm. Otherwise it's the norm of an operator from a subspace of $$\ell_p$$ to $$\ell_p$$.
If you insist on matrix notation, then you can take $$B$$ to be a matrix whose rows form an orthonormal basis of $$W$$. Then $$B^\top B$$ is the orthogonal projection onto $$W$$, and, since it acts as identity on the column span of $$A$$, $$B^\top BA = A$$. Moreover, if $$A$$ has full column rank, then $$BA$$ is an invertible square matrix. So, using the substitution $$z = BAx$$, you get
$$\min_{x \neq 0}\frac{\|\mathcal{A}x\|_p}{\|x\|_p} = \min_{x \neq 0}\frac{\|B^\top BAx\|_p}{\|x\|_p} = \min_{z \neq 0}\frac{\|B^\top z\|_p}{\|(BA)^{-1}z\|_p} = \left(\max_{z \neq 0}\frac{\|(BA)^{-1}z\|_p}{\|B^\top z\|_p} \right)^{-1}$$ This is the inverse of the $$\mathcal{B}_p \to \ell_p$$ operator norm of $$(BA)^{-1}$$, where $$\mathcal{B}_p$$ is the norm on $$\mathbb{R}^n$$ defined by $$\|z\|_{\mathcal{B}_p} = \|B^\top z\|_p$$. (Of course this is the same as above: the subspace $$(W, \|\cdot \|_p)$$ of $$\ell_p$$ is isometric to the normed space $$(\mathbb{R}^n, \|\cdot\|_{\mathcal{B}_p})$$; we've just committed to some basis for it.)