# Least-squares solution

• May 26th 2007, 06:23 PM
ecotheory
Least-squares solution
You'll be able to tell this question is not from a real math student, but here goes ...

Given a set of vectors v_i for i = {1 ... n} in R, I'd like to find the set of vectors in a one-dimensional subspace of R, with basis b, that minimizes the sum of squares of v_i-a_i*b, where a_i for i = {1 ... n} are scalars.

I believe this is almost, but not quite, a simple linear regression problem. But I had no luck setting it up in such a way that MatLab would spit out an answer, since both the set of scalars and the basis b are unknowns. Is there no solution?

Thanks for any help.
• May 26th 2007, 10:02 PM
JakeD
Quote:

Originally Posted by ecotheory
You'll be able to tell this question is not from a real math student, but here goes ...

Given a set of vectors v_i for i = {1 ... n} in R, I'd like to find the set of vectors in a one-dimensional subspace of R, with basis b, that minimizes the sum of squares of v_i-a_i*b, where a_i for i = {1 ... n} are scalars.

I believe this is almost, but not quite, a simple linear regression problem. But I had no luck setting it up in such a way that MatLab would spit out an answer, since both the set of scalars and the basis b are unknowns. Is there no solution?

Thanks for any help.

There is an issue with the statement of the problem: $\displaystyle v_i - a_i b$ is a vector for each $\displaystyle i,$ so what are the "squares" of vectors? Do you mean the sum of the dot products:

$\displaystyle \sum_i (v_i - a_i b) \cdot (v_i - a_i b) = \sum_i (v_i - a_i b)^T (v_i - a_i b)?$

If so, that is not at all a simple linear regression, which minimizes

$\displaystyle (y - a c - b x)^T (y - a c - b x) = \sum_{j=1}^n (y_j - a - b x_j)^2 ,$

where $\displaystyle a, b$ are scalars and $\displaystyle y = [y_1, y_2, \ldots, y_n],$ $\displaystyle c = [1,1, \dots, 1],$ and $\displaystyle x = [x_1, x_2, \ldots, x_n]$ are vectors.

What is the source of this problem?
• May 26th 2007, 10:33 PM
ecotheory
Thanks, I did not mean squares of the vectors. I was thinking of the vector norms, so yes. Minimize the sum of dot products.

I should have said:
Given a set of vectors v_i = {v_1, ..., v_n} in R, describe the set of vectors in a one-dimensional subspace of R, with basis b, that minimizes the sum of squares of the norm of v_i-a_i*b, where a_i = {a_1, ..., a_n} are scalars.

The motivation for the problem is that I am seeking a method for finding a matrix with rank=1 which can be considered most "similar" to a given square matrix. In my phrasing of the problem, I have considered the rows of the matrix as vectors v. While their may be a different approach, I really would like an answer in terms of scalars a and a vector b.

• May 26th 2007, 11:42 PM
JakeD
Quote:

Originally Posted by ecotheory
Thanks, I did not mean squares of the vectors. I was thinking of the vector norms, so yes. Minimize the sum of dot products.

I should have said:
Given a set of vectors v_i = {v_1, ..., v_n} in R, describe the set of vectors in a one-dimensional subspace of R, with basis b, that minimizes the sum of squares of the norm of v_i-a_i*b, where a_i = {a_1, ..., a_n} are scalars.

The motivation for the problem is that I am seeking a method for finding a matrix with rank=1 which can be considered most "similar" to a given square matrix. In my phrasing of the problem, I have considered the rows of the matrix as vectors v. While their may be a different approach, I really would like an answer in terms of scalars a and a vector b.

So is this the problem?

Minimize

$\displaystyle Q = \sum_{i=1}^n || v_{i} - a_i b ||^2 = \sum_{i=1}^n \sum_{j=1}^m (v_{ij} - a_i b_j)^2$

with respect to $\displaystyle a_i,\ i = 1,\ldots, n$ and $\displaystyle b_j,\ j = 1, \ldots, m.$ ($\displaystyle m$ is the dimension of the vectors $\displaystyle v_i$ and $\displaystyle b.$)

I'd think you could put that problem directly into an nonlinear optimization program in Matlab.

Or following the usual minimization technique for solving the problem, set all the partial derivatives

$\displaystyle \partial Q/ \partial a_i = \partial Q/\partial b_j = 0.$

This yields the equations

$\displaystyle a_i = \sum_j v_{ij} b_j / \sum_k b_k^2 ,$
$\displaystyle b_j = \sum_i v_{ij} a_i / \sum_k a_k^2 .$

Then perhaps those equations could be put into a nonlinear equation solver.

Note: It seems to me there is a bit of freedom in the problem in that the vector $\displaystyle b$ can be scaled arbitrarily and the $\displaystyle a_i$ adjusted accordingly. So you may want to add a constraint like

$\displaystyle || b ||^2 = \sum_j b_j^2 = 1 .$
• May 27th 2007, 12:47 PM
JakeD
Quote:

Originally Posted by JakeD
So is this the problem?

Minimize

$\displaystyle Q = \sum_{i=1}^n || v_{i} - a_i b ||^2 = \sum_{i=1}^n \sum_{j=1}^m (v_{ij} - a_i b_j)^2$

with respect to $\displaystyle a_i,\ i = 1,\ldots, n$ and $\displaystyle b_j,\ j = 1, \ldots, m.$ ($\displaystyle m$ is the dimension of the vectors $\displaystyle v_i$ and $\displaystyle b.$)

I'd think you could put that problem directly into an nonlinear optimization program in Matlab.

Or following the usual minimization technique for solving the problem, set all the partial derivatives

$\displaystyle \partial Q/ \partial a_i = \partial Q/\partial b_j = 0.$

This yields the equations

$\displaystyle a_i = \sum_j v_{ij} b_j / \sum_j b_j^2 ,$
$\displaystyle b_j = \sum_i v_{ij} a_i / \sum_j a_i^2 .$

Then perhaps those equations could be put into a nonlinear equation solver.

Note: It seems to me there is a bit of freedom in the problem in that the vector $\displaystyle b$ can be scaled arbitrarily and the $\displaystyle a_i$ adjusted accordingly. So you may want to add a constraint like

$\displaystyle || b ||^2 = \sum_j b_j^2 = 1 .$

I wrote a little program that solves these equations using a simple nonlinear Gauss-Seidel iterative method. It works, so using a nonlinear equation solver is possible.

An interesting fact: if the vectors $\displaystyle v_i$ are the unit vectors on the axes, any unit vector $\displaystyle b$ is a solution. This caused me much confusion trying to verify my program was working. The following proposition gives the reason. First note that when $\displaystyle b$ is a unit vector, the above formulas give $\displaystyle a_i = v_i^T b.$

Proposition: If $\displaystyle v_i,\ i = 1, \ldots, n,$ are the unit vectors on the axes of $\displaystyle R^n$ and $\displaystyle b$ is any unit vector, then $\displaystyle Q = \sum_{i=1}^n || v_{i} - (v_i^T b) b ||^2 = n-1$.
• May 27th 2007, 04:17 PM
ecotheory
That pretty much works. I was able to use the 'fmincon' function in Matlab to get an answer. Thanks a lot.