Least-squares solution

**ecotheory** · May 26th 2007, 06:23 PM

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.

**JakeD** · May 26th 2007, 10:02 PM

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: $v_i - a_i b$ is a vector for each $i,$ so what are the "squares" of vectors? Do you mean the sum of the dot products:

$\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

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

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

What is the source of this problem?

**ecotheory** · May 26th 2007, 10:33 PM

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.

Thanks for your question/clarification.

**JakeD** · May 26th 2007, 11:42 PM

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.

Thanks for your question/clarification.

So is this the problem?

Minimize

$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 $a_i,\ i = 1,\ldots, n$ and $b_j,\ j = 1, \ldots, m.$ ( $m$ is the dimension of the vectors $v_i$ and $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

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

This yields the equations

$a_i = \sum_j v_{ij} b_j / \sum_k b_k^2 ,$
$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 $b$ can be scaled arbitrarily and the $a_i$ adjusted accordingly. So you may want to add a constraint like

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

**JakeD** · May 27th 2007, 12:47 PM

Originally Posted by JakeD

So is this the problem?

Minimize

$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 $a_i,\ i = 1,\ldots, n$ and $b_j,\ j = 1, \ldots, m.$ ( $m$ is the dimension of the vectors $v_i$ and $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

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

This yields the equations

$a_i = \sum_j v_{ij} b_j / \sum_j b_j^2 ,$
$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 $b$ can be scaled arbitrarily and the $a_i$ adjusted accordingly. So you may want to add a constraint like

$|| 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 $v_i$ are the unit vectors on the axes, any unit vector $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 $b$ is a unit vector, the above formulas give $a_i = v_i^T b.$

Proposition: If $v_i,\ i = 1, \ldots, n,$ are the unit vectors on the axes of $R^n$ and $b$ is any unit vector, then $Q = \sum_{i=1}^n || v_{i} - (v_i^T b) b ||^2 = n-1$ .

**ecotheory** · May 27th 2007, 04:17 PM

That pretty much works. I was able to use the 'fmincon' function in Matlab to get an answer. Thanks a lot.

Thread: Least-squares solution

LinkBack

Thread Tools

Display

Least-squares solution

Similar Math Help Forum Discussions

Least Squares solution

Least-squares Solution z of the Overdetermined System

Least Squares Solution for a Parabola

least-squares solution

least-squares solution

Search Tags