<p>Suppose that <span class="math-container">$A$</span> is an <span class="math-container">$m\times n$</span> matrix, and let <span class="math-container">$\mathcal{A}$</span> be the corresponding linear operator whose matrix (w.r.t. the standard basis) is <span class="math-container">$A$</span>. Let <span class="math-container">$W\subseteq \mathbb{R}^m$</span> be the span of the columns of <span class="math-container">$A$</span>, or, equivalently, the range of <span class="math-container">$\cal A$</span>. I am going to treat <span class="math-container">$\mathcal{A}$</span> as an operator from <span class="math-container">$\mathbb{R}^n$</span> to <span class="math-container">$W$</span>. As long as <span class="math-container">$A$</span> has full column rank, the operator <span class="math-container">$\mathcal{A}$</span> is an injection, so it is invertible on its range: let <span class="math-container">$\mathcal{A}^{-1}:W \to \mathbb{R}^n$</span> be its inverse.</p>

<p>You are asking about the quantity
<span class="math-container">$$
\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}
$$</span></p>

<p>So, your quantity <span class="math-container">$f_p(A)$</span> is the operator norm of <span class="math-container">$\mathcal{A}^{-1}$</span>, taken as an operator from the normed space <span class="math-container">$(W, \|\cdot\|_p)$</span> to <span class="math-container">$(\mathbb{R}^n, \|\cdot\|_p)$</span>. In the special case when <span class="math-container">$A$</span> is square, this is just an <span class="math-container">$\ell_p \to \ell_p$</span> operator norm. Otherwise it's the norm of an operator from a <em>subspace</em> of <span class="math-container">$\ell_p$</span> to <span class="math-container">$\ell_p$</span>.</p>

<p>If you insist on matrix notation, then you can take <span class="math-container">$B$</span> to be a matrix whose rows form an orthonormal basis of <span class="math-container">$W$</span>. Then <span class="math-container">$B^\top B$</span> is the orthogonal projection onto <span class="math-container">$W$</span>, and, since it acts as identity on the column span of <span class="math-container">$A$</span>, <span class="math-container">$B^\top BA = A$</span>. Moreover, if <span class="math-container">$A$</span> has full column rank, then <span class="math-container">$BA$</span> is an invertible square matrix. So, using the  substitution <span class="math-container">$z = BAx$</span>, you get</p>

<p><span class="math-container">$$
\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}
$$</span>
This is the inverse of the <span class="math-container">$\mathcal{B}_p \to \ell_p$</span> operator norm of <span class="math-container">$(BA)^{-1}$</span>, where <span class="math-container">$\mathcal{B}_p$</span> is the norm on <span class="math-container">$\mathbb{R}^n$</span> defined by <span class="math-container">$\|z\|_{\mathcal{B}_p} = \|B^\top z\|_p$</span>. (Of course this is the same as above: the subspace <span class="math-container">$(W, \|\cdot \|_p)$</span> of <span class="math-container">$\ell_p$</span> is isometric to the normed space <span class="math-container">$(\mathbb{R}^n, \|\cdot\|_{\mathcal{B}_p})$</span>; we've just committed to some basis for it.)</p>

CC BY-SA 4.0
2018-10-29T19:33:51.037Z
2018-10-30T04:23:20.627Z
2018-10-30T04:23:20.627Z
Sasho Nikolov
<p>I considered a minimization version of matrix p-norms, defined for a matrix <span class="math-container">$A$</span> by</p>

<p><span class="math-container">$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$</span></p>

<p>Notice that <span class="math-container">$f_p(A) = 0$</span> if and only if <span class="math-container">$A$</span>'s columns are linearly dependent.
Therefore <span class="math-container">$f_p(A)$</span> can be seen as a measure of the linear independence of <span class="math-container">$A$</span>'s columns:
the larger <span class="math-container">$f_p(A)$</span> is, the more independent <span class="math-container">$A$</span>'s columns are.</p>

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

CC BY-SA 4.0
2018-10-28T15:58:06.113Z
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
CC BY-SA 4.0
2018-10-29T03:22:23.147Z
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
CC BY-SA 4.0
2018-10-29T05:02:33.383Z
Oh right— the sphere, not the ball!
Aryeh
CC BY-SA 4.0
2018-10-29T12:14:37.757Z
@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
<cc.complexity-theory><ds.algorithms><optimization><machine-learning><unique-games-conjecture>
Minimization version of matrix p-norms?
Octopus
# Minimization version of matrix p-norms?

(Asked by: username_0 on 2018-10-28)

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?

**Tags:** cc.complexity-theory, ds.algorithms, optimization, machine-learning, unique-games-conjecture

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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. @username_1 this problem is equivalent to minimizing $\|Ax\|_p$ over the unit *sphere* of $\ell_p$, which is not a convex set.  
> **username_1**: Oh right— the sphere, not the ball!  
> **username_0**: @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?  

---

## 1 answers

### Answer by username_2 on 2018-10-29. Score: 1

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


---

