Results 1 to 6 of 6

Math Help - 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: 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?
    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

    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 .
    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

    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.
    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: August 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: November 14th 2008, 08:17 PM
  5. least-squares solution
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 12th 2008, 06:43 PM

Search Tags


/mathhelpforum @mathhelpforum