Solving linear system of equations in Lp 
Author Message
 Solving linear system of equations in Lp

Hi-
Is there a numerical method for minimizing Ax=b in Lp.
I mean I want to minimize over x, ||Ax-b||^p.

I guess conjugate gradient can be used here but I don't know how.

I would greatly appreciate any help.
Thanks,
V



Sat, 12 Nov 2005 06:50:09 GMT
 Solving linear system of equations in Lp

Some parts of this question I understand. I assume that
LP means linear programming.

The title says "Solving linear system of equations in Lp"
I assume this question means whether solving a system of
equations can be formulated as a linear programming
problem. The answer is yes: just use a dummy objective.
Using an advanced basis (all variables basic and all
equations nonbasic) this can be done in 0 Simplex iterations.
For an example see: http://www.gams.com/~erwin/lineq/lineq.pdf.

Minimizing Ax=b is somewhat confusing to me. So I'll
skip that.

You could misuse LP to calculate least squares solutions, but LP
is more well known to solve the Least Absolute Deviation
(LAD) also known as L1 norm minimization. Some examples
are given in: http://www.gams.com/~erwin/stats/ols.pdf.
Interestingly LAD was used earlier than Least Squares: the first
LAD based fitting problem goes back to the work of
Boscovitch around 1757, while Legendre published his
"Principle of Least Squares" in 1805.

----------------------------------------------------------------
Erwin Kalvelagen
GAMS Development Corp., http://www.gams.com

----------------------------------------------------------------


Quote:
> Hi-
> Is there a numerical method for minimizing Ax=b in Lp.
> I mean I want to minimize over x, ||Ax-b||^p.
> I guess conjugate gradient can be used here but I don't know how.
> I would greatly appreciate any help.
> Thanks,
> V



Sat, 12 Nov 2005 07:20:23 GMT
 Solving linear system of equations in Lp

Quote:

> Some parts of this question I understand. I assume that
> LP means linear programming.

> The title says "Solving linear system of equations in Lp"
> I assume this question means whether solving a system of
> equations can be formulated as a linear programming
> problem. The answer is yes: just use a dummy objective.
> Using an advanced basis (all variables basic and all
> equations nonbasic) this can be done in 0 Simplex iterations.
> For an example see: http://www.gams.com/~erwin/lineq/lineq.pdf.

> Minimizing Ax=b is somewhat confusing to me. So I'll
> skip that.

But this was his main point!  Instead of a "least squares" solution of
Ax = b, i.e. to minimize ||Ax-b||^2, the idea is to replace the
Euclidean norm by an Lp norm.

I remember Les Karlovitz wrote an article on best approximation in L^p
many years ago.  You can probably also find references in books on best
approximation.

If J denotes the duality map for L^p, i.e. J(f) = |f|^{p-1}*sgn(f), so
that <J(f),f> = ||f||^p and ||J(f)|| = ||f||^(p-1), i.e. if J is the
gradient of 1/p ||.||^p, then a minimizer will satisfy <J(Af-b), Af> =
0.  This is a nonlinear system of equations.

--Ron Bruck



Sat, 12 Nov 2005 08:24:30 GMT
 Solving linear system of equations in Lp

Quote:

> Some parts of this question I understand. I assume that
> LP means linear programming.

> The title says "Solving linear system of equations in Lp"
> I assume this question means whether solving a system of
> equations can be formulated as a linear programming
> problem. The answer is yes: just use a dummy objective.
> Using an advanced basis (all variables basic and all
> equations nonbasic) this can be done in 0 Simplex iterations.
> For an example see: http://www.gams.com/~erwin/lineq/lineq.pdf.

> Minimizing Ax=b is somewhat confusing to me. So I'll
> skip that.

> You could misuse LP to calculate least squares solutions, but LP
> is more well known to solve the Least Absolute Deviation
> (LAD) also known as L1 norm minimization. Some examples
> are given in: http://www.gams.com/~erwin/stats/ols.pdf.
> Interestingly LAD was used earlier than Least Squares: the first
> LAD based fitting problem goes back to the work of
> Boscovitch around 1757, while Legendre published his
> "Principle of Least Squares" in 1805.

> ----------------------------------------------------------------
> Erwin Kalvelagen
> GAMS Development Corp., http://www.gams.com

> ----------------------------------------------------------------


>> Hi-
>> Is there a numerical method for minimizing Ax=b in Lp.
>> I mean I want to minimize over x, ||Ax-b||^p.

>> I guess conjugate gradient can be used here but I don't know how.

>> I would greatly appreciate any help.
>> Thanks,
>> V

He means Lp as in Banach space:
integral{|f(x)|^p}dx.  In case of a vector of complex numbers
this is ||Ax-b||^p = sum over i{|y_i|^p} where y = Ax-b.

fourierr at fastermail dot com
--
Posted via http://web2news.com the faster web2news on the web



Sat, 12 Nov 2005 08:30:46 GMT
 Solving linear system of equations in Lp

Ah, sorry about that.
I was working on a linear programming model, so that explained
the short circuit between my ears.....

----------------------------------------------------------------
Erwin Kalvelagen
GAMS Development Corp., http://www.gams.com

----------------------------------------------------------------


Quote:
> He means Lp as in Banach space:



Sat, 12 Nov 2005 09:17:01 GMT
 Solving linear system of equations in Lp

Quote:

> Hi-
> Is there a numerical method for minimizing Ax=b in Lp.
> I mean I want to minimize over x, ||Ax-b||^p.

> I guess conjugate gradient can be used here but I don't know how.

You feed a CG or BFGS program the function value

f(x)= p^-1 ||Ax-b||_p^p= p^-1 sum_i

(this transformation makes the gadient simpler) and its gradient,

g(x)= sum_i |(Ax-b)_i|^(p-1) a_i,

where a_i is the transpose of the i-th row of A.

The solution of the least squares problem might be a good starting point.

Arnold Neumaier



Sat, 12 Nov 2005 20:05:46 GMT
 Solving linear system of equations in Lp


Quote:

>Hi-
>Is there a numerical method for minimizing Ax=b in Lp.
>I mean I want to minimize over x, ||Ax-b||^p.

>I guess conjugate gradient can be used here but I don't know how.

>I would greatly appreciate any help.
>Thanks,
>V

rather than using the norm directly, minimize its p-th power i.e

   sum_{i=1 to N} (sum_{j=1 to n} a_ij*x_j -b_i)^p

where N is the number of rows of A and n the number of columns.
ths is now no longer a qaudratic problem in x, but could nevertheless be treated
as a smooth unconstrained optimization problem. there have been described
iterative methods using a weigthed least squares problem in each step.
see Ake Bjoerck: solving least sqaures problems (SIAM) pages 172 ff.
you should be wawre of the fact that for large p the problem is not that easy
since the norm then behaves like the nonsmooth infinity norm.
hope that helps
peter



Sat, 12 Nov 2005 22:49:32 GMT
 Solving linear system of equations in Lp

reverently intoned up the aether:

Quote:
> Hi-
> Is there a numerical method for minimizing Ax=b in Lp.
> I mean I want to minimize over x, ||Ax-b||^p.

> I guess conjugate gradient can be used here but I don't know how.

> I would greatly appreciate any help.
> Thanks,
> V

Try the course notes at the following link:

http://www.math.washington.edu/~burke/crs/516/

These notes should be reasonably up to date and if you can work
through them you will be ready to wander out and read the latest
journal articles on the subject.

A simple introduction to theory can be found in the course notes at:

http://www.math.washington.edu/~burke/crs/515/

The only change you are making here is to shift from working with a
quadratic function ||Ax-b|| to some other polynomial which may not be
as well behaved.  i.e., p=1 (mod 2) implies that your objective is no
longer twice continuously differentiable as there may be a sharp
corner in you function near the zero(s).

enjoy,

Sean

"In the End, we will remember not the words of our enemies,
 but the silence of our friends."

- Martin Luther King Jr. (1929-1968)




Thu, 17 Nov 2005 04:32:20 GMT
 Solving linear system of equations in Lp

Quote:

> Hi-
> Is there a numerical method for minimizing Ax=b in Lp.
> I mean I want to minimize over x, ||Ax-b||^p.

> I guess conjugate gradient can be used here but I don't know how.

> I would greatly appreciate any help.
> Thanks,
> V

Iterated reweighted least squares.

http://www-sop.inria.fr/robotvis/personnel/zzhang/Publis/Tutorial-Est...



Tue, 22 Nov 2005 23:05:16 GMT
 
 [ 9 post ] 

 Relevant Pages 

1. Solving linear system of equations in Lp

2. Solving a non linear system of equations but with linear part

3. Solving a system of linear equations

4. Solve a linear equation system over GF(2)

5. solving a system of linear equations

6. Solving an overdetermined system of linear equations?

7. Solving a system of nin-linear equations in C++

8. Help wanted: Solving linear equation system

9. URGENT: Solving underdetermined linear equation systems with SVD

10. Solving sparse systems of linear equations

11. Solving complex system of linear equations

12. Solving a system of linear equations with LAPACK.


 
Powered by phpBB® Forum Software