Me and two friends of mine are working on a project (scholarly purposes only). The goal of this project is to clean an audio signal (speech, a song, anything audio) of echo.
Generally speaking, if $x(n)$ is the clean audio signal, without the echo, then the signal with the echo is $y(n)=x(n)+ax(n-d)$, signal is just a synonym for function, just think of it as functions.
In short: We know function $y: \mathbb N \to \mathbb R$, our goal is to find function $x: \mathbb N \to \mathbb R$, $a \in (0,1)$ and $d\in \mathbb N-\{0\}$ such that $y(n)=x(n)+ax(n-d)$.
What we did:
First thing we did was to find $d$. We can use the autocorrelation function:
$\Phi_{xx}(k)=\sum_{n\in \mathbb Z}x(n)x(n-k)$. This function $\Phi_{xx}(k)$ describes the similarity between the function $x(n)$ and itself in different points in time.
We were given $y(n)$, so we can find $\Phi_{yy}(k)$. From the definition of $\Phi$, we know that the maximum value of $\Phi(k)$ will be at $k=0$, and it will have a local maximum at $k=d$.
And that is exactly what we did. To find $d$, we found where the local maximum of $\Phi(k)$ is achieved, that is $d$. This seems to agree with logic and real world tests that we performed. So from now on, assume $d$ is known.
The problem:
The problem is finding $a$. We cant seem to find a way to find $a$. We know that $y(n)=x(n)$ where $n<d$, so one method would be to say $y(d)=x(d)-x(0)$. We know $y(d)$, we know $x(0)$ (which is equal to $y(0)$), but we don't have a way of finding $x(d)$, so this is not the way.
another approach would be to use the autocorrelation again:
$\Phi_{yy}(k)=\sum_{n \in \mathbb Z}y(n)y(n-k)=\sum_{n \in \mathbb Z}[x(n)+ax(n-d)][x(n-k)+ax(n-d-k)]=\sum_{n \in \mathbb Z}x(n)x(n-k)+a\sum_{n \in \mathbb Z}x(n)x(n-d-k)+a\sum_{n \in \mathbb Z}x(n-d)x(n-k)+a^2\sum_{n \in \mathbb Z}x(n-d)x(n-d-k)=\Phi_{xx}(k)+a\Phi_{xx}(k+d)+a\Phi_{xx}(k-d)+a^2\Phi_{xx}(k)$.
We know $\Phi_{yy}$, so we know $\Phi_{yy}(0)$ in particular, so we can say:
$\Phi_{yy}(0)=\Phi_{xx}(0)+a\Phi_{xx}(d)+a\Phi_{xx}(-d)+a^2\Phi_{xx}(0)=1+2a\Phi_{xx}(d)+a^2$, but that's not useful because we don't know $\Phi_{xx}(d)$ and have no way of finding it since we do not know $x(n)$ yet.
If anyone has any other ideas on how to find $a$ given only $y$ and $d$, I'd be very grateful.
What about formulating it as an optimization problem? The problem is one of estimating a linear system with unknown input, where the system is given by
$$ \mathbf{A} = \left[ \begin{array}{c} 1 & 0 & \cdots & a & 0 & \cdots \\ 0 & 1 & 0 & \cdots & 0 & a & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array} \right], $$
where the number of zeros between each $1$ and $a$ is equal to $d$. So you could solve something like
$$ ( \mathbf{x},a)^\ast = \operatorname{arg}\min_{\mathbf{x},a} \,\,\, {\frac{1}{2}}\left \Vert \mathbf{Ax} - \mathbf{y} \right \Vert_2^2 \;\;\;\;\; \mathrm{s.t.} \;\;\;\;\; a > 0 $$
The gradient w.r.t. $\mathbf{x}$ is just $\mathbf{A}^\mathrm{T} \mathbf{A} - \mathbf{A}^{\mathrm{T}}\mathbf{y}$. The gradient w.r.t. $a$ isn't obvious to me but I'm sure you could work it out.