1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fabee Aug 23 '13 at 7:22
  • $\begingroup$ @fabee I believe he wants to minimize the sample variance. $\endgroup$ – AnonSubmitter85 Aug 23 '13 at 7:28
  • 2
    $\begingroup$ 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? $\endgroup$ – AnonSubmitter85 Aug 23 '13 at 7:36
  • $\begingroup$ @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$. $\endgroup$ – fabee Aug 23 '13 at 7:37
  • $\begingroup$ @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. $\endgroup$ – AnonSubmitter85 Aug 23 '13 at 7:39
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Hi AnonSubmitter85, I am lost on your LS solution. I wonder why $Ax=\vec{1}y^TAx-c$? $\endgroup$ – Tom Bennett Aug 23 '13 at 20:06
  • $\begingroup$ 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? $\endgroup$ – Tom Bennett Aug 23 '13 at 20:47
  • $\begingroup$ @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? $\endgroup$ – AnonSubmitter85 Aug 24 '13 at 0:49
  • $\begingroup$ @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? $\endgroup$ – AnonSubmitter85 Aug 24 '13 at 0:53
  • 1
    $\begingroup$ @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? $\endgroup$ – AnonSubmitter85 Aug 25 '13 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.