Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #7049 > unrolled thread

Findminimum too slow for iterative reweighted least squares

Started byAlberto Maydeu-Olivares <amaydeu@gmail.com>
First post2011-12-09 10:59 +0000
Last post2011-12-13 10:52 +0000
Articles 3 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  Findminimum too slow for iterative reweighted least squares Alberto Maydeu-Olivares <amaydeu@gmail.com> - 2011-12-09 10:59 +0000
    Re: Findminimum too slow for iterative reweighted least squares "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-12-10 12:35 +0000
    Re: Findminimum too slow for iterative reweighted least squares Ray Koopman <koopman@sfu.ca> - 2011-12-13 10:52 +0000

#7049 — Findminimum too slow for iterative reweighted least squares

FromAlberto Maydeu-Olivares <amaydeu@gmail.com>
Date2011-12-09 10:59 +0000
SubjectFindminimum too slow for iterative reweighted least squares
Message-ID<jbspn1$3rf$1@smc.vnet.net>
Hi, I'm trying to use FindMinimum to minimize a weighted least squares
function where the weight matrix needs to be updated at each
iteration. The weight matrix involves the inverse of a symbolic
matrix. This should be fast if FindMinimum first evaluates the
symbolic matrix, then takes the inverse. Given how long it takes, it's
obviously not doing that. I wonder if anyone can suggest a way to
force FindMinimum to do that. I obviously tried Evaluate, but does not
work. At attach a toy example so that you can try. Finding the minimum
of this toy example takes a full second. It takes minutes to do a
realistic size job, It should not take more than a couple of seconds.

Thanks a lot for your help.


model = {l1^2 + ps, l2*l1, l2^2 + ps, l3*l2, l3*l1, l3^2 + ps};
theta = {l1, l2, l3, ps};
j = Outer[D, model, theta];
data = {2., .42, 3., .56, .48, 1.};
startval = Transpose[{theta, {.5, .5, .5, .5}}];
e = data - model;
mat = {{2 (l1^2 + ps)^2, 2 l1 l2 (l1^2 + ps), 2 l1^2 l2^2,
    2 l2 l3 (l1^2 + ps), 2 l1 l2^2 l3,
    2 l2^2 l3^2}, {2 l1 l2 (l1^2 + ps),
    ps (l2^2 + ps) + l1^2 (2 l2^2 + ps), 2 l1 l2 (l2^2 + ps),
    l1 l3 (l1^2 + l2^2 + ps), l2 l3 (l1^2 + l2^2 + ps),
    2 l1 l2 l3^2}, {2 l1^2 l2^2, 2 l1 l2 (l2^2 + ps), 2 (l2^2 + ps)^2,
     2 l1^2 l2 l3, 2 l1 l3 (l2^2 + ps),
    2 l1^2 l3^2}, {2 l2 l3 (l1^2 + ps), l1 l3 (l1^2 + l2^2 + ps),
    2 l1^2 l2 l3, l2^2 l3^2 + (l1^2 + ps) (l3^2 + ps),
    l1 l2 (2 l3^2 + ps), 2 l2 l3 (l3^2 + ps)}, {2 l1 l2^2 l3,
    l2 l3 (l1^2 + l2^2 + ps), 2 l1 l3 (l2^2 + ps),
    l1 l2 (2 l3^2 + ps), l1^2 l3^2 + (l2^2 + ps) (l3^2 + ps),
    2 l1 l3 (l3^2 + ps)}, {2 l2^2 l3^2, 2 l1 l2 l3^2, 2 l1^2 l3^2,
    2 l2 l3 (l3^2 + ps), 2 l1 l3 (l3^2 + ps), 2 (l3^2 + ps)^2}};

(*brute force approach to benchmark*)
w = Inverse[mat];
irls = FindMinimum[e. w  . e, Evaluate[Sequence @@ startval], Gradient
-> -2 e.   w .j]; // Timing

(*this should work, in fact, it takes almost twice as long*)
w := Inverse[mat];
irls = FindMinimum[Evaluate[e. w  . e],  Evaluate[Sequence @@
startval], Gradient -> Evaluate[-2 e.   w .j]]; // Timing

[toc] | [next] | [standalone]


#7079

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-12-10 12:35 +0000
Message-ID<jbvjn7$j1e$1@smc.vnet.net>
In reply to#7049
On Fri, 09 Dec 2011 10:59:45 -0000, Alberto Maydeu-Olivares  
<amaydeu@gmail.com> wrote:

> Hi, I'm trying to use FindMinimum to minimize a weighted least squares
> function where the weight matrix needs to be updated at each
> iteration. The weight matrix involves the inverse of a symbolic
> matrix. This should be fast if FindMinimum first evaluates the
> symbolic matrix, then takes the inverse. Given how long it takes, it's
> obviously not doing that. I wonder if anyone can suggest a way to
> force FindMinimum to do that. I obviously tried Evaluate, but does not
> work. At attach a toy example so that you can try. Finding the minimum
> of this toy example takes a full second. It takes minutes to do a
> realistic size job, It should not take more than a couple of seconds.
>
> Thanks a lot for your help.
>
>
> model = {l1^2 + ps, l2*l1, l2^2 + ps, l3*l2, l3*l1, l3^2 + ps};
> theta = {l1, l2, l3, ps};
> j = Outer[D, model, theta];
> data = {2., .42, 3., .56, .48, 1.};
> startval = Transpose[{theta, {.5, .5, .5, .5}}];
> e = data - model;
> mat = {{2 (l1^2 + ps)^2, 2 l1 l2 (l1^2 + ps), 2 l1^2 l2^2,
>     2 l2 l3 (l1^2 + ps), 2 l1 l2^2 l3,
>     2 l2^2 l3^2}, {2 l1 l2 (l1^2 + ps),
>     ps (l2^2 + ps) + l1^2 (2 l2^2 + ps), 2 l1 l2 (l2^2 + ps),
>     l1 l3 (l1^2 + l2^2 + ps), l2 l3 (l1^2 + l2^2 + ps),
>     2 l1 l2 l3^2}, {2 l1^2 l2^2, 2 l1 l2 (l2^2 + ps), 2 (l2^2 + ps)^2,
>      2 l1^2 l2 l3, 2 l1 l3 (l2^2 + ps),
>     2 l1^2 l3^2}, {2 l2 l3 (l1^2 + ps), l1 l3 (l1^2 + l2^2 + ps),
>     2 l1^2 l2 l3, l2^2 l3^2 + (l1^2 + ps) (l3^2 + ps),
>     l1 l2 (2 l3^2 + ps), 2 l2 l3 (l3^2 + ps)}, {2 l1 l2^2 l3,
>     l2 l3 (l1^2 + l2^2 + ps), 2 l1 l3 (l2^2 + ps),
>     l1 l2 (2 l3^2 + ps), l1^2 l3^2 + (l2^2 + ps) (l3^2 + ps),
>     2 l1 l3 (l3^2 + ps)}, {2 l2^2 l3^2, 2 l1 l2 l3^2, 2 l1^2 l3^2,
>     2 l2 l3 (l3^2 + ps), 2 l1 l3 (l3^2 + ps), 2 (l3^2 + ps)^2}};
>
> (*brute force approach to benchmark*)
> w = Inverse[mat];
> irls = FindMinimum[e. w  . e, Evaluate[Sequence @@ startval], Gradient
> -> -2 e.   w .j]; // Timing
>
> (*this should work, in fact, it takes almost twice as long*)
> w := Inverse[mat];
> irls = FindMinimum[Evaluate[e. w  . e],  Evaluate[Sequence @@
> startval], Gradient -> Evaluate[-2 e.   w .j]]; // Timing
>

The reason for the poor performance is simply that w is a huge expression.  
In the second case you've not only inserted Evaluate but also changed Set  
for SetDelayed on w so that the inverse has to be re-calculated at each  
iteration. You can get better performance like this:

w = Simplify@Inverse[mat];
irls = FindMinimum[
  Evaluate[e.w.e], Evaluate[Sequence @@ startval],
  Gradient -> Evaluate[-2 e.w.j]
]; // Timing

If FindMinimum needs to perform a lot of iterations (which is not the case  
in the example above), you may like to try:

w = Simplify@Inverse[mat];
ewe = Compile[Evaluate@Thread[{theta, _Real, 0}],  
Evaluate@Simplify[e.w.e]];
irls = FindMinimum[
  ewe[Sequence @@ theta], Evaluate[Sequence @@ startval],
  Gradient -> Evaluate[-2 e.w.j]
]; // Timing

[toc] | [prev] | [next] | [standalone]


#7181

FromRay Koopman <koopman@sfu.ca>
Date2011-12-13 10:52 +0000
Message-ID<jc7aoq$p0d$1@smc.vnet.net>
In reply to#7049
On Dec 9, 2:59 am, Alberto Maydeu-Olivares <amay...@gmail.com> wrote:
> [...]
> model = {l1^2 + ps, l2*l1, l2^2 + ps, l3*l2, l3*l1, l3^2 + ps};
> theta = {l1, l2, l3, ps};
> j = Outer[D, model, theta];
> data = {2., .42, 3., .56, .48, 1.};
> startval = Transpose[{theta, {.5, .5, .5, .5}}];
> e = data - model;
> mat = {{2 (l1^2 + ps)^2, 2 l1 l2 (l1^2 + ps), 2 l1^2 l2^2,
>   2 l2 l3 (l1^2 + ps), 2 l1 l2^2 l3,
>   2 l2^2 l3^2}, {2 l1 l2 (l1^2 + ps),
>   ps (l2^2 + ps) + l1^2 (2 l2^2 + ps), 2 l1 l2 (l2^2 + ps),
>   l1 l3 (l1^2 + l2^2 + ps), l2 l3 (l1^2 + l2^2 + ps),
>   2 l1 l2 l3^2}, {2 l1^2 l2^2, 2 l1 l2 (l2^2 + ps), 2 (l2^2 + ps)^2,
>    2 l1^2 l2 l3, 2 l1 l3 (l2^2 + ps),
>   2 l1^2 l3^2}, {2 l2 l3 (l1^2 + ps), l1 l3 (l1^2 + l2^2 + ps),
>   2 l1^2 l2 l3, l2^2 l3^2 + (l1^2 + ps) (l3^2 + ps),
>   l1 l2 (2 l3^2 + ps), 2 l2 l3 (l3^2 + ps)}, {2 l1 l2^2 l3,
>   l2 l3 (l1^2 + l2^2 + ps), 2 l1 l3 (l2^2 + ps),
>   l1 l2 (2 l3^2 + ps), l1^2 l3^2 + (l2^2 + ps) (l3^2 + ps),
>   2 l1 l3 (l3^2 + ps)}, {2 l2^2 l3^2, 2 l1 l2 l3^2, 2 l1^2 l3^2,
>   2 l2 l3 (l3^2 + ps), 2 l1 l3 (l3^2 + ps), 2 (l3^2 + ps)^2}};
> [...]

Interesting model. Is the order ... l3*l2, l3*l1 ... intentional, or
were the two inadvertently reversed? And are the corresponding data
values (.56, .48) in the right order? In any case, 'mat' seems to be
the correct normal-theory covariance matrix for the model as given.

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web