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