Is there an analytic solution to the weighted least squares problem?

Hi All,

Is there an analytic / noniterative way to find a minimizer of  || W * ( A
x - b) ||  over x, where || . || is the Euclidean norm, and W is a diagonal
positive weighting matrix?  

For a simpler special case one can assume A is a nonsingular matrix of
size (m x n) where m > n. (In other words A is full-rank, tall and
skinny.)

Your help will be most appreciated.

Thanks,
Emre

I should add that I am interested in an efficient solution when A has a
known structure (like sparse, lower triangular, etc.) so that solving (A\b)
is relatively easy. I would like to avoid forming or factoring W * A, if
possible.

Emre

On Aug 9, 2:29&#4294967295;pm, "emre" <egu...@ece.neu.edu> wrote:
> Hi All,
>
> Is there an analytic / noniterative way to find a minimizer of &#4294967295;|| W * ( A
> x - b) || &#4294967295;over x, where || . || is the Euclidean norm, and W is a diagonal
> positive weighting matrix? &#4294967295;
>
[snip]

If W is a diagonal matrix, can't you just multiply things through
and get a classical least-squares problem?

let x' = Wx, and b' = Wb

then you have || A x' - b' || ?

On 9 Aug, 21:41, "emre" <egu...@ece.neu.edu> wrote:
> I should add that I am interested in an efficient solution when A has a
> known structure (like sparse, lower triangular, etc.) so that solving (A\b)
> is relatively easy.

Why would you solve A\b in an LMS problem?

> I would like to avoid forming or factoring W * A, if
> possible.

That's my suggestion: Multiply through to get minimize

min  { WA(Wb-Wx) }

and use the standard methods.

Rune

>If W is a diagonal matrix, can't you just multiply things through
>and get a classical least-squares problem?
>
>let x' =3D Wx, and b' =3D Wb
>
>then you have || A x' - b' || ?

Actually W does not commute with A in general since its diagonals are not
necessarily constant.

Still, as Rune suggested, it is possible to also change the matrix by B =
W A and solve for ||B x' -b'|| but this may ruin the structure in A. For
example, when A is made up of orthonormal columns, the least squares
solution to A x = b is given simply by  x = transpose(A) * b. However B
does not carry this property, therefore solving B x' = b' is not as easy.

Emre

>Why would you solve A\b in an LMS problem?

Sorry for using Matlab slang:  By A\b I meant the least-squares solution
to A x = b, which is exactly  what you get when you type A\b in Matlab.

>> I would like to avoid forming or factoring W * A, if
>> possible.
>
>That's my suggestion: Multiply through to get minimize
>
>min  { WA(Wb-Wx) }
>
>and use the standard methods.

As I explained in my reply to Julius, the point is to take advantage of
the structure in A, and forming W*A may ruin this.. Alternatively it would
be useful to know whether using the structure in A is not at all
possible..

Thank you both,

Emre

On 10 Aug, 06:52, "emre" <egu...@ece.neu.edu> wrote:
> >Why would you solve A\b in an LMS problem?
>
> Sorry for using Matlab slang: &#4294967295;By A\b I meant the least-squares solution
> to A x = b, which is exactly &#4294967295;what you get when you type A\b in Matlab.
>
> >> I would like to avoid forming or factoring W * A, if
> >> possible.
>
> >That's my suggestion: Multiply through to get minimize
>
> >min &#4294967295;{ WA(Wb-Wx) }
>
> >and use the standard methods.
>
> As I explained in my reply to Julius, the point is to take advantage of
> the structure in A, and forming W*A may ruin this..

It might. But what is most important to you? Preserve tha structure
of A or find a solution to the problem?

> Alternatively it would
> be useful to know whether using the structure in A is not at all
> possible..

People have been dealing with these sorts of things for decades
already. Try to look up e.g. the Finite Elment Method and see
how they minimize functions by solving large, sparse systems.

Rune

>> As I explained in my reply to Julius, the point is to take advantage of
>> the structure in A, and forming W*A may ruin this..
>
>It might. But what is most important to you? Preserve tha structure
>of A or find a solution to the problem?

Rune, preserving the structure of A is not important per se. However,
solving a system of equations in the LS sense is computationally less
expensive when there is structure.  What is important to me is finding an
*efficient* solution.  

Your point is well taken, one could think of taking the hard way, assuming
it needs to be done once or twice. However, when such a system needs to be
solved many times sequentially (as in solving an optimization problem using
Newton's method), efficiency is essential, especially when dealing with
large dimensional problems.

>People have been dealing with these sorts of things for decades
>already. Try to look up e.g. the Finite Elment Method and see
>how they minimize functions by solving large, sparse systems.

Thanks for pointing that out. I realized there is no problem when A is
sparse, since W*A can be kept as sparse, and the solution is usually much
easier than its full counterpart.  Still, I am wondering if I there is an
efficient solution when W*A is not structured, but A is. One case of
interest is when A has orthonormal columns.

Emre

On 10 Aug, 15:03, "emre" <egu...@ece.neu.edu> wrote:

> Your point is well taken, one could think of taking the hard way, assuming
> it needs to be done once or twice. However, when such a system needs to be
> solved many times sequentially (as in solving an optimization problem using
> Newton's method), efficiency is essential, especially when dealing with
> large dimensional problems.

Again, these problems are not new. Computational fluid dynamics
is among the hardest computational problems around. Try and find
literature or talk with people in that area.

> >People have been dealing with these sorts of things for decades
> >already. Try to look up e.g. the Finite Elment Method and see
> >how they minimize functions by solving large, sparse systems.
>
> Thanks for pointing that out. I realized there is no problem when A is
> sparse, since W*A can be kept as sparse,

Are you sure? Are you talking about general W or diagonal or
maybe tridiagonal W? Is '*' the usual matrix product or the
Schur product?

> and the solution is usually much
> easier than its full counterpart. &#4294967295;Still, I am wondering if I there is an
> efficient solution when W*A is not structured, but A is. One case of
> interest is when A has orthonormal columns.

These are the classical tradeoffs in numerical computations: Sparse
matrices work well with iterative solution methods, since only a few
computations are required per stage. Once you start messing with
matrix multiplications one usually get dense matrices.

If you want efficient solutions look for parrallel solution methods.
With the availablility of multi-CPU computers that's where the
potential lies. Again, check out CFD and other heavy-duty computation
applications; that's where you find the knowledgeable people and
where
the progress is made.

Rune

On 2008-08-10 01:43:49 -0300, "emre" <eguven@ece.neu.edu> said:

>> If W is a diagonal matrix, can't you just multiply things through
>> and get a classical least-squares problem?
>> 
>> let x' =3D Wx, and b' =3D Wb
>> 
>> then you have || A x' - b' || ?
> 
> Actually W does not commute with A in general since its diagonals are not
> necessarily constant.
> 
> Still, as Rune suggested, it is possible to also change the matrix by B =
> W A and solve for ||B x' -b'|| but this may ruin the structure in A. For
> example, when A is made up of orthonormal columns, the least squares
> solution to A x = b is given simply by  x = transpose(A) * b. However B
> does not carry this property, therefore solving B x' = b' is not as easy.
> 
> Emre

Ake Bjorck has looked at both least squares and sparse matrix computations.
His book on "Numerical Methods for Least Squares Problems" published by SIAM
is a standard. Ask google for his home page which has lots of references to
his many articles and conference presentation.