2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aryeh Oct 28 '18 at 15:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 29 '18 at 3:22
  • $\begingroup$ Oh right— the sphere, not the ball! $\endgroup$ – Aryeh Oct 29 '18 at 5:02
  • $\begingroup$ @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? $\endgroup$ – Octopus Oct 29 '18 at 12:14
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.