# linear problem with $\|.\|_\infty$ and $\|.\|_1$ norm constraints

I have a question regarding a straightforward linear algebra problem, yet the solution is (at least for me) not trivial.

Assume the sequences $\phi_i$ with coefficients $\phi_i[n]\in\mathbb{R}$, and coefficients $b_i\in\mathbb{R}$ given by the problem. Now the objective is solving the following linear problem for $u[n]$

$$\begin{bmatrix} \phi_0 &\ldots &\phi_0[k_f]\\ \vdots & &\vdots\\ \phi_I &\ldots &\phi_I[k_f]\\ \end{bmatrix}u[n] = \begin{bmatrix} sign(b_0)\\ \vdots\\ sign(b_I)\\ \end{bmatrix}$$ where $k_f>I$ and we have additional restrictions $\|\phi_i\|_1=1$ (for all $i$) and $\|u\|_\infty\leq1$. This could have a solution, and if so many more since the $\phi$ matrix is underdetermined (and thus the null space of the matrix can be used to generate more solutions).

Let me give you a simple example

$$\begin{bmatrix} 0.5 &-0.3 &0.2\\ 0.1 &-0.8 &0.1\\ \end{bmatrix}\begin{bmatrix} 1\\ -1\\ 1\\ \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ \end{bmatrix}.$$ Note that this only works since the $\phi$ matrix and $b$ matrix match in sign. If the signs are changed contrary to each other, it is not possible to construct $u[n]$ only using 1 or -1 (that's a simple choice although not the real restriction; the absolute value of the coefficients should be smaller or equal to 1).

Now my real question: how would the entire solution set to my problem look like? and is it maybe possible to define more constraints on $\phi_i$ such that we will not need the constraint on $u[n]$ anymore? Maybe there is no single good answer here, but I'm just looking for some insights.

I hope it is clear for all and that we can share some thoughts, thanks in advance!

UPDATE 3-12-2015 Seems that the problem is also not that trivial for the readers... So let me test some insights I got during the past couple of days. Please feel free to discuss them, as I am not sure they are 100% right.

CASE $k_f>I$ Solving the linear problem in MATLAB will return $u[n]$ with least Euclidian norm (if I'm right), but this doesn't guarantee $\|u\|_\infty\leq 1$. Also a lot of other solutions exist since the problem is underdetermined. With the columns of the null matrix we can construct other solutions (and maybe one with $\|u\|_\infty\leq1$). The problem now is that, following the rank-nullity theorem, the null matrix will be overdetermined, making it impossible to exactly construct a given solution $u[n]$ in a non trail and error way.

CASE $k_f=I$ Let me first give you the following example

$$\begin{bmatrix} 0.6 &-0.4\\ 0.3 &-0.7\\ \end{bmatrix}\begin{bmatrix} 1\\ -1\\ \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ \end{bmatrix}.$$ Trying to construct a different solution $u[n]$ that doesn't satisfy $\|u\|_\infty\leq1$, we find that this is impossible as long as the rows of the $\phi$ matrix are linearly independent and the columns match in sign (if also the $b_i$s match in sign). For instance [3;2] would match the first row, but not the second. SO for this case it looks like restricting the $\phi$ matrix in the described way could indeed make the restriction on $u[n]$ redundant.

CASE $k_f<I$ is not interesting since this case is overdetermined and will probably only be able to give a solution in minimal least squares form (or something similar).

• Welcome and nice first question! – Eff Dec 1 '15 at 9:57