Simple Newton's Method Fractal code in MATLAB

Due to popular request I've sharing some very simple Newton's Method Fractal code in MATLAB. It produces the following 800x800 image (in about 2.5 seconds on my 2.4Ghz Macbook Pro):


>> [niters,solutions] = matlab_fractal;
>> imagesc(niters)

function [niters,solutions] = matlab_fractal
%Create Newton's Method Fractal Image
%Tomasz Malisiewcz (tomasz@cmu.edu)
%http://quantombone.blogspot.com/
NITER = 40;
threshold = .001;

[xs,ys] = meshgrid(linspace(-1,1,800), linspace(-1,1,800));
solutions = xs(:) + i*ys(:);
select = 1:numel(xs);
niters = NITER*ones(numel(xs), 1);

for iteration = 1:NITER
oldi = solutions(select);

%in newton's method we have z_{i+1} = z_i - f(z_i) / f'(z_i)
solutions(select) = oldi - f(oldi) ./ fprime(oldi);

%check for convergence or NaN (division by zero)
differ = (oldi - solutions(select));
converged = abs(differ) < threshold;
problematic = isnan(differ);

niters(select(converged)) = iteration;
niters(select(problematic)) = NITER+1;
select(converged | problematic) = [];
end

niters = reshape(niters,size(xs));
solutions = reshape(solutions,size(xs));

function res = f(x)
res = (x.^2).*x - 1;

function res = fprime(x)
res = 3*x.^2;

when you outgrow homework-code: a real CRF inference library to the rescue

I have recently been doing some CRF inference for an object recognition task and needed a good ol' Max-Product Loopy Belief Propagation. I revived my old MATLAB-based implementation that grew out of a Probabilistic Graphical Models homework. Even though I had vectorized the code and had tested it for correctness -- would my own code be good enough on problems involving thousands of nodes and arities as high as 200? It was the first time I ran my own code on such large problems and I wasn't surprised when it took several minutes for those messages to stop passing.

I tried using Talya Meltzer's MATLAB package for inference in Undiracted Graphical Models. It is a bunch of MATLAB interfaces to efficient C code. Talya is Yair Weiss's PhD student (so that basically makes her an inference expert).

It was nice to check my old homework-based code and see the same beliefs for a bunch of randomly generated binary planar-grid graphs. However, for medium sized graphs her code was running in ~1 second while my homework code was taking ~30 seconds. That was a sign that I had outgrown my homework-based code. While I was sad to see my own code go, it is a sign of maturity when your research problems mandate a better and more-efficient implementation of such a basic inference algorithm. Her package was easy to use, has plenty of documentation, and I would recommend it to anybody in need of CRF inference.