O algoritmo Remez

14

O algoritmo Remez é uma rotina iterativa conhecida para aproximar uma função por um polinômio na norma minimax. Mas, como Nick Trefethen [1] diz sobre isso:

A maioria dessas [implementações] remonta há muitos anos e, de fato, a maioria delas não resolve o melhor problema geral de aproximação, como exposto acima, mas variantes envolvendo variáveis ​​discretas ou filtragem digital. Pode-se encontrar alguns outros programas de computador em circulação, mas, no geral, parece que atualmente não existe um programa amplamente utilizado para calcular as melhores aproximações.

Pode-se calcular a solução minimax também aplicando otimização de mínimos quadrados ou convexa, por exemplo, usando Matlab e a caixa de ferramentas CVX gratuita aplicada à função Runge em [-1, 1]:

m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc                         % 0.17 sec for Matlab, CVX and SeDuMi

A aproximação com os polinômios de Chebyshev possui uma norma minimax, 0.1090enquanto essa abordagem aqui atinge um mínimo de 0.0654, o mesmo valor que é calculado com o algoritmo Remez na chebfuncaixa de ferramentas Matlab .

Existe alguma vantagem em aplicar o algoritmo Remez mais complicado se você puder calcular a solução minimax de maneira mais rápida e precisa com um solucionador de otimização? Existem relatórios / artigos comparando essas duas abordagens em alguns problemas difíceis ou casos de teste?

-
[1] R. Pachon e LN Trefethen. Matemática Numérica do BIT (2008) vol. 46

Hans W.
fonte

Respostas:

4

A resposta "certa" depende muito do motivo pelo qual você precisa do seu aproximant. Você realmente precisa da melhor aproximação para algum erro vinculado? Ou apenas uma boa aproximação? Ou apenas uma boa aproximação no sentido minmax?

Nick Trefethen recentemente deu um bom exemplo, onde a aproximação Remez é uma má ideia, pois minimiza o erro máximo, independentemente do erro médio em todo o intervalo, que pode não ser o que você deseja. Obviamente, o erro máximo pode ser grande, mas isso é limitado para funções suaves.

Atualizar

Após a discussão nos comentários abaixo, baixei o CVX Toolbox e fiz uma comparação direta com o algoritmo Chebfun Remez (aviso: faço parte da equipe de desenvolvimento Chebfun):

% Do the convex optimization bit.
m = 101; n = 11;            % 101 points, polynomial of degree 10
xi = linspace(-1, 1, m);    % equidistant points in [-1, 1]
ri = 1 ./ (1+(5*xi).^2);    % Runge function

tic                         % p is the polynomial of degree (n-1)
cvx_begin                   % minimize the distance in all points
    variable p(n);
    minimize( max(abs(polyval(p, xi) - ri)) );
cvx_end
toc_or = toc                % 0.17 sec for Matlab, CVX and SeDuMi

% Extract a Chebfun from the result
x = chebfun( [-1,1] );
A = [ chebfun(1) , x ];
for k=3:n, A(:,k) = A(:,k-1).*x; end
or = A * flipud(p)

% Make a chebfun of Runge's function
f = chebfun( @(x) 1 ./ ( 1 + 25*x.^2 ) )

% Get the best approximation using Remez
tic, cr = remez( f , 10 ); toc_cr = toc

% Get the maximum error in each case
fprintf( 'maximum error of convex optimization: %e (%f s)\n' , norm( f - or , inf ) , toc_or );
fprintf( 'maximum error of chebfun remez: %e (%f s)\n' , norm( f - cr , inf ) , toc_cr );

% Plot the two error curves
plot( [ f - cr , f - or ] );
legend( 'chebfun remez' , 'convex optimization' );

Depois de muita produção, recebo, no meu laptop, o Matlab 2012a, CVX versão 1.22 e o mais recente SVN Snapshot da Chebfun:

maximum error of convex optimization: 6.665479e-02 (0.138933 s)
maximum error of chebfun remez: 6.592293e-02 (0.309443 s)

Observe que o Chebfun fusado para medir o erro tem precisão de 15 dígitos. Remez, da Chebfun, leva o dobro do tempo, mas recebe um erro global menor. Deve-se ressaltar que o CVX usa código compilado para a otimização, enquanto o Chebfun é 100% nativo do Matlab. O erro mínimo de 0.00654é o erro mínimo 'na grade', fora dessa grade, o erro pode ser de até 0.00659. Aumentando o tamanho da grade para m = 1001obter

maximum error of convex optimization: 6.594361e-02 (0.272887 s)
maximum error of chebfun remez: 6.592293e-02 (0.319717 s)

ou seja, quase a mesma velocidade, mas a otimização discreta ainda é pior a partir do quarto dígito decimal. Por fim, aumentando ainda mais o tamanho da grade para m = 10001obter

maximum error of convex optimization: 6.592300e-02 (5.177657 s)
maximum error of chebfun remez: 6.592293e-02 (0.312316 s)

ou seja, a otimização discreta agora é dez vezes mais lenta e ainda é pior a partir do sexto dígito.

O ponto principal é que o Remez obterá o resultado ideal globalmente. Embora o analógico discreto possa ser rápido em redes pequenas, ele não fornecerá um resultado correto.

Pedro
fonte
E N. Trefethen estava enfatizando o mesmo e deu um exemplo semelhante no artigo que eu estava citando. A questão não era sobre a melhor aproximação, mas: Qual é a vantagem do algoritmo Remez (hoje em dia) se você pode obter o mesmo resultado com um solucionador convexo razoável ?
Hans W.
1
@ HansWerner, desculpe, eu interpretei mal sua pergunta. Seu solucionador convexo não está fornecendo o mesmo resultado, pelo menos não para todos os dígitos. Se entendi seu código convexo corretamente, você está minimizando o erro máximo em um conjunto discreto de pontos. Essa é uma boa aproximação - mas não é a mesma que - minimizar o erro máximo global.
Pedro
O solucionador convexo neste caso deu um resultado melhor . Pense nisso, o algoritmo Remez é um procedimento iterativo, bastante semelhante a uma rotina de otimização, e também não retornará um resultado exato. No caso concreto acima, a solução da otimização foi melhor, ou seja, tinha uma norma máxima geral menor do que o resultado da melhor implementação de Remez que eu conheço. A questão ainda está em aberto .
27560 Hans Hans
@HansWerner, como você mediu o erro máximo da solução obtida com o solucionador convexo? O algoritmo Remez chebfundeve iterar até que o mínimo seja alcançado para a precisão da máquina (em certo sentido).
Pedro Pedro
Não necessariamente; existem opções como 'tol' (que é tolerância relativa) ou 'maxiter' para chebfun/remez, mas existem opções semelhantes para todos os tipos de solucionadores de otimização. De certa forma, o Remez é uma rotina de otimização especializada para uma determinada tarefa. E a pergunta é: os solucionadores de propósito geral alcançaram e não há mais necessidade de um solucionador tão especializado? Claro, posso estar errado.
27560 Hans Hans