Deconvolution (Linear Convolution) with an Under Determined System of Equations? If I have a measured signal $\mathbf{y}$ which is the result of the true signal $\mathbf{x}$ convolved with another function (linear and not circular convolution), I always seem to get an underdetermined system. Convolution expressed as a matrix equation:

\begin{equation}
\mathbf{y} = \mathbf{A} \mathbf{x}
\end{equation}

I am interested in finding $\mathbf{x}$, given $M=5$ observations and knowing that the convolution matrix is defined by a boxcar function of window length $n=3$. The corresponding $M\times N$ convolution matrix is defined as the following, where $N=M+n-1$.
\begin{equation}
\mathbf{A} = \begin{pmatrix}
1 &amp;   1 &amp;   1 &amp;   0 &amp;   0 &amp;   0 &amp;   0 \\ 
0 &amp;   1 &amp;   1 &amp;   1 &amp;   0 &amp;   0 &amp;   0 \\ 
0 &amp;   0 &amp;   1 &amp;   1 &amp;   1 &amp;   0 &amp;   0 \\ 
0 &amp;   0 &amp;   0 &amp;   1 &amp;   1 &amp;   1 &amp;   0 \\ 
0 &amp;   0 &amp;   0 &amp;   0 &amp;   1 &amp;   1 &amp;   1 \\ 
\end{pmatrix}
\end{equation}

In the literature, the convolution matrix is often $N\times N$ (or $M\times{}M$, however you want to define it). But it seems that with a finite number of observations, the convolution matrix corresponding to the available observations would have to be $M \times (M+n-1)$, which is always underdetermined (except when $n \equiv 1$, in which you don't have convolution of your signal). 

In most convolution/deconvolution examples, the matrix is often represented as being "square," in which there exist rows in the matrix where the number of non-zero elements are less than $n$. This does not correspond to any possible measurement. Padding is common for the input signal ($\mathbf{x}$) but not for the output ($\mathbf{y}$), so how can the system not be underdetermined?

Edit for clarification:

I understand that convolution matrix is traditionally written as $N+m+1$:

\begin{equation}
  \mathbf{A} = \begin{pmatrix}
    1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
    1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
    1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
    0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\
    0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0\\
    0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0\\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1\\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1\\
    0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1
  \end{pmatrix}
\end{equation}

In practice, you never measure the signals corresponding to the first two and last two rows, so it would seem that you cannot use this matrix for creating the deconvolution filter.
On the contrary, if you compute the convolution of a signal $x$ having a span of $M$ non-zero entries with a filter with a span of $N$ non-zero entries, then the resulting sequence will have $M+N-1$ non-zero entries, so that your system should be over-determined.

Computing the minimizer $x$ of $\|[0,1,0]*y-[1,1,1]*x\|_2$ leads by standard variational methods to the system of equations

$$[0,1,1,1,0]*y=[1,2,3,2,1]*x$$

with the first two and the last two removed, and for some reason mathematics / linear algebra claims that this system is solvable even if $[0,1,0]*y=[1,1,1]*x$ is not.