0
$\begingroup$

Let $A$ be a $n\times c$ matrix and $b\geq 0$ (element-wise) be a given $n\times 1$ vector. $A$ has following properties

  • $n>c$ and $rank(A)=c$.
  • Any choice of $c$ rows of $A$ is linearly independent.
  • $A$ is element-wise positive.

    Question: Let $x$ be any given non-negative vector such that $\|x\|_0\geq 1$. Is $$\|Ax-b\|_0\leq c$$ where $\|\cdot\|_0$ denotes the $\ell_0$-norm

$\endgroup$
1
  • $\begingroup$ @user1551 udpated $\endgroup$ Apr 25, 2020 at 17:22

1 Answer 1

0
$\begingroup$

This isn't true. E.g. $$ \left\|\pmatrix{1&0\\ 0&1\\ 1&1\\ 1&2}\pmatrix{\frac23\\ \frac13}-\pmatrix{1\\ 1\\ 1\\ 1}\right\|_0 =\left\|\frac13\pmatrix{-1\\ -2\\ 0\\ 1}\right\|_0 =3>c=2. $$ Note that in this example, $b\not\in\operatorname{ran}(A)$ and $x=A^+b$.

$\endgroup$
1
  • $\begingroup$ nice to see you after a long time. This requires $b$ to lie in column-space of $A$, if that is not true, then will this still hold? $\endgroup$ Apr 25, 2020 at 18:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .