# Minimize Variance of a Linear Function

I have the following problem. I wan to minimize the variance of $Ax+c$, where $A$ is a matrix, $x$ and $c$ are vectors. I want to find $x=\arg \min_x var(Ax+c)$.

How would you solve this?

• Hi Tom, can you be a bit more specific? Do you mean the variance over the vector entries? Is $A$ square or can it have any shape? What have you tried already? – fabee Aug 23 '13 at 7:22
• @fabee I believe he wants to minimize the sample variance. – AnonSubmitter85 Aug 23 '13 at 7:28
• If you let $y = [1/N;1/N;\cdots;1/N]$ such that the mean of $(Ax+c)$ is $y^{T}(Ax+c)$, can you then differentiate $((Ax+c)-y^{T}(Ax+c))^2$ and set it to zero? – AnonSubmitter85 Aug 23 '13 at 7:36
• @AnonSubmitter85 What I don't understand is: If $x$ are vectors, then $y = Ax+c$ is a vector as well. Does he mean $\mbox{var}(y)=\frac{1}{n}\sum_i (y_i - \overline y)^2$ in which case it would work for a single vector, or does he mean $\mbox{cov}(y)$ in which case he'd have to specify what minimizing variance meant. In the former case, one could of course additionally minimize the variance over the vector entries w.r.t. different samples $x_i$. – fabee Aug 23 '13 at 7:37
• @fabee I believe he means the former, $\operatorname{var}(y)$, and the $x_i$ that will minimize it. That is, he wants to find the vector $x$ such that the sample variance of $Ax+c$ is minimal. – AnonSubmitter85 Aug 23 '13 at 7:39

Let $y = [1/N; 1/N; \dots; 1/N]$ such that $y^{\mathrm{T}}\left(Ax+c\right)$ is the mean of $(Ax+c)$. Then differentiate $\Vert (Ax+c) - y^{\mathrm{T}}\left(Ax+c\right) \Vert_2^2$, set it equal to zero, and then solve for $x$.

Edit:

Here's another possible way that just uses the usual least squares approach. Let $\vec{1}\in\mathbb{R}^m$ be a vector of all 1's and $y\in\mathbb{R}^m$ be as above. Then we want the LS approximation to

$$Ax = \vec{1}y^{\mathrm{T}}(Ax+c) - c$$

Using the normal equations, this works out to

$$\begin{array}{c} \left(A^{\mathrm{T}}A - A^{\mathrm{T}}\vec{1}y^{\mathrm{T}}A\right)x = A^{\mathrm{T}} \, \vec{1}y^{\mathrm{T}} c - A^{\mathrm{T}}c \\ \Rightarrow x = \left(A^{\mathrm{T}}A - A^{\mathrm{T}}\vec{1}y^{\mathrm{T}}A\right)^{-1} \left( A^{\mathrm{T}} \,\vec{1}y^{\mathrm{T}} c - A^{\mathrm{T}}c \right) \end{array}$$

You can try each of these. If they are correct, they will give the same answer.

To test the above, I used the following in Matlab:

A = rand(5,5);         # Random input.
c = rand(5,1);         # Random input.
y = 1/5 * ones(5,1);   # Mean computing vector.

# Q is the matrix we need to invert. It is not full
# rank, so we use the psuedo-inverse to get the minimum
# norm solution, though any solution is equally correct.
Q = ( A' * A - A' * ones(5,1) * y' * A );
x = pinv(Q) * ( A' * ones(5,1) * y' * c - A' * c );

# See what variance this answer gives.
var( A*x + c )

ans =

1.2942e-31

# Since Q has rank N-1, we know there are infinitely many
# solutions along a line in R^N. We know the nullspace has
# dimension 1, so we don't have to check its size.
n = null(Q);
var( A * (x + 100*rand(1)*n) + c )

ans =

2.4297e-28

• Hi AnonSubmitter85, I am lost on your LS solution. I wonder why $Ax=\vec{1}y^TAx-c$? – Tom Bennett Aug 23 '13 at 20:06
• One question: $(Ax+c)-\vec{1}y^t (Ax+c)=(I-\vec{1}y^T)(Ax+c)$. We want to minimize the norm of this. However, $(I-\vec{1}y^T)$ has rank $N-1$ as the sum of the columns are required to be 0. In this case, what would be the LS solution? – Tom Bennett Aug 23 '13 at 20:47
• @TomBennett I think the right side should actually be $\vec{1}y^{T}(Ax+c) - c$, no? Is that why you are asking? Sorry about that. The process is the same and the answer is only slightly different. Can you figure it out from here? – AnonSubmitter85 Aug 24 '13 at 0:49
• @TomBennett I don't understand why you're trying to invert $I-\vec{1}y^T$. The system we want to solve is $Ax = \vec{1}y^{T}(Ax+c) - c$, so make the error orthogonal to the range of $A$ by forcing it to be in the nullspace of $A^T$. Thus, we want $A^T \left( Ax - \vec{1}y^{T}(Ax+c) + c \right) = 0$. Is that what you are getting at? – AnonSubmitter85 Aug 24 '13 at 0:53
• @TomBennett Doesn't that just mean that there is a whole line of solutions and that you can pick any one of them to get the minimum variance? For instance, if you have $By_0 = z$ with $\operatorname{rank}(B)=N-1$, then $y = y_0 + \alpha \hat{y}$ where $\alpha\in\mathbb{R}$ and $\hat{y}\in\operatorname{nullspace}(B)$ is also a solution. So I'd suggest you find a particular solution and then extend by also finding the basis vector of the nullspace. Does that make sense? – AnonSubmitter85 Aug 25 '13 at 3:20