1

All matrices are real. $A$ is a matrix of size $n \times k$ with $k < n$ and has independent columns.

The function $v(x) = \|Ax\|_1$ is a norm.

What is the matrix norm induced by $v$? Is it of the form $\|F (\cdot) Q\|_1$ for some $F$ and $Q$ which are easy functions of $A$.

By easy I mean functions made of matrix sum, matrix multiplication, pseudoinverse, transpose, matrices from SVD (or other well-known decomposition) of $A$ etc.

I was trying along the lines of this post with $y = Ax$, but there is a problem. $$ \max_{x\neq 0}\frac{v(Mx)}{v(x)} =\max_{x\neq 0}\frac{\|AMx\|_1}{\|Ax\|_1} =\max_{\substack{y\neq 0 \\ y \in \text{Range}\color{red}{(A)}}}\frac{\|AMA^\dagger y\|_1}{\|y\|_1} \color{red}{\neq} \|AMA^\dagger\|_1 $$ Here $\dagger$ denotes the Moore-Penrose pseudoinverse.

Community
  • 1
ziutek
  • 1,355
  • 1
    In its present form, the answer to your question is yes, by a circular reasoning. Call the induced norm $N(\cdot)$. It is easy to see that $N(I)=1$. Let $Q=I$ and $F(M)=N(M)I$. Then $|F(M)Q|_1=|N(M)I|_1=N(M)$. You need to be more specific about $F$ to make your question meaningful. – user1551 Dec 07 '14 at 20:41
  • @user1551 Thanks for the brief reply. You are absolutely correct. I modified the question to specify that I meant "easy" functions of $A$. – ziutek Dec 08 '14 at 08:31
  • 1
    Note that $|A|_1$ is the maximum absolute column sum of the matrix $A$. – littleO Dec 08 '14 at 08:36
  • @littleO Yes, I know that but could you give a hint about how this helps answer my question? – ziutek Dec 08 '14 at 08:39

0 Answers0