Results 1 to 6 of 6

Thread: Least-squares solution

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    8

    Question 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by ecotheory View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2007
    Posts
    8
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by ecotheory View Post
    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

    $\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 .$
    Last edited by JakeD; May 27th 2007 at 02:26 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by JakeD View Post
    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$.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2007
    Posts
    8

    Smile

    That pretty much works. I was able to use the 'fmincon' function in Matlab to get an answer. Thanks a lot.
    Last edited by ecotheory; May 27th 2007 at 04:35 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Least Squares solution
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Aug 7th 2010, 05:07 AM
  2. Least-squares Solution z of the Overdetermined System
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 14th 2010, 03:21 AM
  3. Least Squares Solution for a Parabola
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: May 28th 2009, 03:16 AM
  4. least-squares solution
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Nov 14th 2008, 08:17 PM
  5. least-squares solution
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Nov 12th 2008, 06:43 PM

Search Tags


/mathhelpforum @mathhelpforum