Suppose that I solve the following optimization problem:
$$ \underset{\mathbf{x}}{\text{minimize}} \quad || \mathbf{b} - \mathbf{A} \mathbf{x} ||_{2}^{2} $$ $$ \text{subject to} \; \; |x_{i}| = 1 \quad \forall i $$
where $\mathbf{b} \in \mathbb{C}^{M \times 1}$ with $|\mathbf{b}|_{i} \in \{-1, 0, 1, N \}$, $\mathbf{A} \in \mathbb{C}^{M \times N}$ is a lower triangular Toeplitz matrix with $|\mathbf{A}|_{i,j} \leq 1$, and $\mathbf{x} \in \mathbb{C}^{N \times 1}$ and $M > N$.
Can I ever be sure that:
$$\| \mathbf{b} - \mathbf{A} \mathbf{x}_{\ast} \|_{2}^{2} < \| \mathbf{b}\|_{2}^{2}$$
where $\mathbf{x}_{\ast}$ is the optimal solution?
If so, how can I show this? Or perhaps in other words, what are the conditions that allow me to say this?
Subtracting and expanding this out, we get:
$$ \|\mathbf{b}\|_{2}^{2} - 2 \mathbf{b}^{H} \mathbf{A} \mathbf{x}_{\ast} + \mathbf{x}_{\ast}^{H} \mathbf{A}^{H} \mathbf{A} \mathbf{x}_{\ast} - \|\mathbf{b}\|_{2}^{2} < 0 $$
ie that:
$$ \mathbf{x}_{\ast}^{H} \mathbf{A}^{H} \mathbf{A} \mathbf{x}_{\ast} < 2 \mathbf{b}^{H} \mathbf{A} \mathbf{x}_{\ast} $$
But I don't see how that actually tells me anything.
Does anyone have any ideas?
Here is an idea. Since $|x_{i}| = 1$, if we transpose and then take absolute values, we get:
$$ \mathbf{1}^{T} \mathbf{A}^{H} \mathbf{A} \mathbf{1} < 2 \mathbf{1}^{T} | \mathbf{A}^{H} \mathbf{b}| $$
Does that spark any ideas? Hmm...I think the restrictions on the absolute values of the elements will be important here...but I can't figure out how they fit together...
Edit:
The matrix $\mathbf{A}$ is a causal FIR filter matrix -- ie lower triangular and Toeplitz. See: https://www.dsprelated.com/freebooks/filters/Matrix_Filter_Representations.html
You cannot. For instance, consider $$ A = \pmatrix{0&0\\0&0\\1&0}, \quad b = \pmatrix{1\\0\\0}. $$ In this case, we find that all $\|b - Ax\|_2^2 = 2$ for all $x$ satisfying $|x_1| = 1$, but $\|b\|_2^2 = 1$.