0
$\begingroup$

Let $s$ and $d$ be non-negative integers with $0\leq s<d$ and let $v,u\in \mathbb{R}^d$ be vectors satisfying the sparsity estimate $$ \max\{\|u\|_0,\|v\|_0\}\leq d-s, $$ where, as usual, for any vector $x \in \mathbb{R}^d$ we define $\|x\|_0:=\sum_{i=1}^d\,I_{x_i\neq 0}$.

Let $A$ be an $d\times d$-matrix solving $Au=v$. How sparse can $A$ be? I.e.: what is $$ \inf_{A\in L(\mathbb{R}^d),\,Au=v}\, \|A\|_0, $$ where as above $\|A\|_0:=\sum_{i,j=1}^d\,I_{A_{i,j}\neq 0}$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$||v||_0$, so $\leq d-s$: The matrix $A$ needs to have at least one entry for every entry of $v$ (otherwise it can't obtain that entry). It is also sufficient to have so many entries, as if we consider one $j$ with $u_j \not= 0$ (which exists otherwise the system has a solution (the zero matrix) only if $v_i = 0$ for all $i$) then we can set for every entry $v_i \not= 0$ the matrix entry $A_{i,j} = \frac{v_i}{u_j}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry I'm abit confused, what is $A_{i,j}$ when $u_j=0$ or $v_i=0$? $\endgroup$
    – ABIM
    Commented Mar 22, 2022 at 9:05
  • $\begingroup$ When $v_i = 0$ then $A_{i,j} = 0$. We can use an arbitrary $u_j \not= 0$ to find such a matrix. If all $u_j = 0$ then this system has a solution only if also all $v_i = 0$. $\endgroup$
    – Bastian Seifert
    Commented Mar 22, 2022 at 9:24
  • $\begingroup$ I clarified the answer a bit. $\endgroup$
    – Bastian Seifert
    Commented Mar 22, 2022 at 9:25
  • $\begingroup$ Great! Thanks Bastian $\endgroup$
    – ABIM
    Commented Mar 22, 2022 at 9:27

You must log in to answer this question.

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