Least Squares and Auto and Cross Correlation

Question

I am trying to understand why auto and cross correlation helps find the best fit line in least squares. I have an equation as stated here:

$Ax=b$ -- I have not exact solution, so I use the least squares equation. $$A^TAx=A^Tb$$ I can solve and use the equation but I am trying to figure out why cross and auto correlation helps. Can anyone shed some light on that? For example, what do cross and auto correlation represent?

I am learning about signal processing and linerisation of a signal. $A$ is the input unpredistoted signal and $b$ is feedback distorted signal. $x$ is the coefficients that will be used to weight the Look Up Table. $Ax=B$ is solved in the adaptive algorithm box, in the link below.

http://www.altera.com/end-markets/wireless/advanced-dsp/predistortion/wir-digital-predistortion.html

Answer 1

Cross-correlation and auto-correlation are not directly linked to least squares.

Least squares can create a line of best fit for a set of points.

Cross correlation is a measure of the similarity of one signal to another (as a function of time lag to one signal). The discrete (digital) cross-correlation is an array where each element tells you how much the signals correlate with a certain amount of time lag. This operation is performed naively with a sliding window, or faster using Fourier, or other transforms. xcorr(a,b) = IFFT(FFT(a)* conj(FFT(b)))

Auto correlation is a measure of the similarity of a waveform to itself as a function of time.

There are normalised variants of cross-correlation and auto-correlation. These are created by measuring the standard deviation of each signal and dividing the output by the multiple of both. This enables you to classify the level of correlation much more easily. 0 implies no correlation and 1 implies identical signals.

Answer 2

I have seen these terms applied to least squares problems.
If the problem is $Ax=b$. Then A is the matrix of input rows, or if the input was transformed, A is the "design matrix" of transformed rows. X is the weight vector or parameter vector that is being solved for which optimizes the solution. And b is some given model training output or desired values.
The least squares solution is defined as the solution to $A^TAx=A^Tb$. Then $A^TA$ is called autocorrelation and refers to autocorrelation matrix of input or design columns. Each column is a set of the same input feature from all inputs, or a set of the same design feature from all transformed inputs. And $A^Tb$ is the crosscorrelation of the input columns from $A^T$ with the model outputs from $b$. In the general case, the model weights are a matrix $X$ and the model outputs are a matrix $B$. Then the crosscorrelation would be a matrix $A^TB$ of design columns and model output rows corresponding to each input row.
However it doesn't seem that least squares is what you need, but this may help someone else see how the correlation terminology can apply to least squares.

Answer 3

Indeed the Linear Least Squares uses the Covariance (Which resembles Cross Correlation) and the Variance (Which resembles the Auto Correlation) for parameter estimation.

Let's see that using simple example - Linear Function fitting.
Assume our model is given by (Simple Polynomial Model of Order 2):

$$ {y}_{i} = a {x}_{i} + b, \; i = 1, 2, \cdots, n $$

In this model we assume knowing $ \left\{ \left( {x}_{i}, {y}_{i} \right) \right\}_{i = 1}^{n} $ and we're after estimating $ a, b $.
So, we could build this in the form of Ordinary Least Squares:

$$ \boldsymbol{y} = X \boldsymbol{\theta} \Rightarrow \hat{\boldsymbol{\theta}} = {\left( {X}^{T} X \right)}^{-1} {X}^{T} y $$

Let's examine it using basic Math.
Estimating $ b $ using the Least Squared Error:

$$ \hat{b} = \arg \min_{b} \frac{1}{2} \sum_{i = 1}^{n} {\left( {y}_{i} - a {x}_{i} + b \right)}^{2} $$

Taking the Derivative with respect to $ b $ will yield:

$$ \hat{b} = a \sum_{i = 1}^{n} {x}_{i} - \sum_{i = 1}^{n} {y}_{i} = a \bar{x} - \bar{y} $$

Where $ \bar{x} = \sum_{i = 1}^{n} {x}_{i} $ and $ \bar{y} = \sum_{i = 1}^{n} {y}_{i} $.
It suggests that the constant $ a $ is set such that the line must go through the mean of $ \left\{ {x}_{i} \right\}_{i = 1}^{n} $ and $ \left\{ {y}_{i} \right\}_{i = 1}^{n} $. Which indeed makes sense, as this is the mean of the 2D data.

Estimating $ a $ using the Least Squared Error:

$$ \hat{a} = \arg \min_{a} \frac{1}{2} \sum_{i = 1}^{n} {\left( {y}_{i} - a {x}_{i} + b \right)}^{2} $$

Taking the Derivative with respect to $ a $ will yield:

$$\begin{aligned} \frac{\mathrm{d} \frac{1}{2} \sum_{i = 1}^{n} {\left( {y}_{i} - a {x}_{i} + b \right)}^{2} }{\mathrm{d} a} & = -\sum_{i = 1}^{n} {x}_{i} \left( {y}_{i} - a {x}_{i} + b \right) && \text{} \\ & = -\sum_{i = 1}^{n} {x}_{i} {y}_{i} + a \sum_{i = 1}^{n} {x}_{i}^{2} -b \sum_{i = 1}^{n} {x}_{i} && \text{} \\ & = -\sum_{i = 1}^{n} {x}_{i} {y}_{i} + a \sum_{i = 1}^{n} {x}_{i}^{2} - \left( a \bar{x} - \bar{y} \right) \sum_{i = 1}^{n} {x}_{i} && \text{Inserting estimation of $ b $} \\ & = -\sum_{i = 1}^{n} {x}_{i} {y}_{i} + a \sum_{i = 1}^{n} {x}_{i}^{2} - a \sum_{i = 1}^{n} {x}_{i} \bar{x} + \sum_{i = 1}^{n} {x}_{i} \bar{y} && \text{} \\ \Rightarrow a & = \frac{\sum_{i = 1}^{n} {x}_{i} {y}_{i} - \sum_{i = 1}^{n} {x}_{i} \bar{y}}{\sum_{i = 1}^{n} {x}_{i}^{2} - \sum_{i = 1}^{n} {x}_{i} \bar{x}} \end{aligned}$$

It looks like we're close but not right there.
The trick is noting these equations:

$$ \sum_{i = 1}^{n} \left( \bar{x} \bar{y} - {y}_{i} \bar{x} \right) = 0 , \; \sum_{i = 1}^{n} \left( \bar{x}^{2} - {x}_{i} \bar{x} \right) = 0 $$

So now:

$$\begin{aligned} a & = \frac{\sum_{i = 1}^{n} {x}_{i} {y}_{i} - \sum_{i = 1}^{n} {x}_{i} \bar{y}}{\sum_{i = 1}^{n} {x}_{i}^{2} - \sum_{i = 1}^{n} {x}_{i} \bar{x}} && \text{} \\ & = \frac{\sum_{i = 1}^{n} \left( {x}_{i} {y}_{i} - {x}_{i} \bar{y} \right) + \sum_{i = 1}^{n} \left( \bar{x} \bar{y} - {y}_{i} \bar{x} \right)}{\sum_{i = 1}^{n} \left( {x}_{i}^{2} - {x}_{i} \bar{x} \right) + \sum_{i = 1}^{n} \left( \bar{x}^{2} - {x}_{i} \bar{x} \right)} && \text{} \\ & = \frac{ \sum_{i = 1}^{n} \left( {x}_{i} - \bar{x} \right) \left( {y}_{i} - \bar{y} \right) }{ \sum_{i = 1}^{n} \left( {x}_{i} - \bar{x} \right) \left( {x}_{i} - \bar{x} \right) } && \text{} \\ & = \frac{ \frac{1}{n} \sum_{i = 1}^{n} \left( {x}_{i} - \bar{x} \right) \left( {y}_{i} - \bar{y} \right) }{ \frac{1}{n} \sum_{i = 1}^{n} \left( {x}_{i} - \bar{x} \right) \left( {x}_{i} - \bar{x} \right) } && \text{} \\ & = \frac{ \operatorname{Cov} \left( x, y \right) }{ \operatorname{Var} \left( x \right) } \end{aligned}$$

Where we have the sample Covariance and the Sample Variance of the data.

If you're after an intuition why is that, the answer is simple. If wee look at the problem from a probabilistic point of a view we have a linear model. Hence estimating its parameters should be done using the 1st and 2nd moments of the data. This is also matches the Gaussian Case where those moments define the whole distribution.

P. S.
Found also this great answer https://math.stackexchange.com/a/717552/33 (Which is similar).