Summing the entries of a special matrix, pt.2

Continuing on from yesterday, I now reveal the answer for the special case of \(\gamma = 0.5\).
This allows us to use the following expression for the partial sum of a harmonic series
$$
\sum_{m=1}^{n} \frac{1}{m} = \ln n + \gamma_E + \frac{1}{2n} – \frac{1}{12n^2} + \frac{1}{120n^4} + \mathcal{O}(n^{-6})
$$
where \(\gamma_E \approx 0.5772\) is the Euler-Mascheroni constant. Thus,


$$\begin{align}
|| \vd^{0.5} ||^2 & = \sum_{m=1}^{n-1}\sum_{l=m+1}^n \frac{1}{l(n-m+1)} \\
& = \sum_{m=1}^{n-1} \frac{1}{n-m+1} \sum_{l=m+1}^n \frac{1}{l} \\
& = \sum_{m=1}^{n-1} \frac{1}{n-m+1} \left [ \sum_{l=1}^n \frac{1}{l} – \sum_{l=1}^m \frac{1}{l} \right ] \\
& \approx \sum_{m=1}^{n-1} \frac{1}{n-m+1} \left [ \ln n + \gamma_E + \frac{1}{2n} – \frac{1}{12n^2} – \ln m – \gamma_E – \frac{1}{2m} + \frac{1}{12m^2} \right ] \\
& \approx \sum_{m=1}^{n-1} \frac{1}{n-m+1} \left [ \ln n/m – \frac{n-m}{2nm} + \frac{n^2 – m^2}{12n^2m^2} \right ].
\end{align}
$$
And to find \(|| \vc_M^{0.5} ||^2\) we first use partial fractions
and then an approximation of the partial sum of the harmonic series:
$$\begin{align}
|| \vc_M^{0.5} ||^2 & = \sum_{m=M+1}^{n}\sum_{l=1}^m \frac{1}{l(m-l+1)} \\
& = \sum_{m=M+1}^{n} \frac{1}{m+1} \sum_{l=1}^m \frac{1}{l} + \frac{1}{m-l+1} \\
& \approx \sum_{m=M+1}^{n} \frac{1}{m+1} \left [ \ln m + \gamma_E + \frac{1}{2m} – \frac{1}{12m^2} + \sum_{l=1}^m \frac{1}{l} \right ] \\
& \approx 2 \sum_{m=M+1}^{n} \frac{1}{m+1} \left ( \ln m + \gamma_E + \frac{1}{2m} – \frac{1}{12m^2} \right ).
\end{align}
$$
With these expressions we avoid double sums in calculating the bounds
for the special case of \(\gamma = 0.5\), with a small price paid in error.
The figure below shows just how much error there is in this approximation of the geometric norm as a function of \(M\) for \(n=500\).
That is an error I can live with. (MATLAB code is attached below.)
bounderror.jpg
Now, I have some open questions about this, and the business of approximating the sum of the elements of this matrix to estimate \(\langle \vv_{i}, \vv_{q} \rangle\):

  1. First, is there just as simple a single-sum expression for any \(\gamma > 0\)?
  2. Second, the approach of grouping and summing the antidiagonals of the matrix is not the quickest way to approach \(\langle \vv_{i}, \vv_{q} \rangle\) since it ignores the fact that the gradients in \(\MA_{iq}\) do not point in the same directions, i.e., for \(1 \le l,m \le n\):
    $$
    \nabla [\MA_{iq}]_{ml} = \nabla m^{-\gamma} l^{-\gamma} = – m^{-\gamma} l^{-\gamma} \left [
    \begin{array}{c}
    \gamma/m \\
    \gamma/l
    \end{array}
    \right ].$$
    Is there a simple way to know at iteration \(M\) at which \(M\) elements of \(\MA_{iq} \bullet \MG_{iq}\) I should look to likely find its largest remaining values?
  3. Finally, for this strategy, what is the resulting bound on the remainder and its approximation using a smart single sum approximation like that I derived above?

BEGIN MATLAB CODE


clear all;  % essential for avoiding wasting time debuging stupidity
n = 500;
gamma = 0.5;  % special case, do not change

% evaluate || \vd ||^2 directly
vdl2 = 0;
for mm=1:n-1
  for ll=mm+1:n
    vdl2 = vdl2 + (1/(ll*(n-mm+1)))^(2*gamma);
  end
end

% evaluate || \vc_M ||^2 directly
vcl2 = zeros(n,1);
for M=2:n
  for mm=M+1:n
    for ll=1:mm
      vcl2(M) = vcl2(M) + (1/(ll*(mm-ll+1)))^(2*gamma);
    end
  end
end

% now find approximate without the double sum stupidity above
mm=1:n-1;
% approximate || \vd ||^2
dcf = sum(1./(n-mm+1).*(log(n./mm) – …
  0.5*(n – mm)./(n.*mm) + (1/12)*(n^2 – mm.^2)./(n.*mm).^2));
% approximate || \vc_M ||^2
ccf = zeros(n,1);
for M=2:n
  for mm=M+1:n
    ccf(M) = ccf(M) + 2*(log(mm)+0.5772156649015328606065 + …
      0.5./mm – (1/12)./(mm.^2))/(mm+1);
  end
end

% create figure
f0 = figure(‘Position’,[300 300 700 400],’Units’,’Normalized’);
set(f0,’PaperPosition’,[0.18 0.3 3*6 3*4],’PaperType’,’usletter’, …
  ‘PaperOrientation’,’portrait’);
% Paper size is so large because of some strange issues
% with MATLAB on my Sparse Approximation Station,
% which has a 33 inch screen, by the way
width = 0.82; h = 0.83;
top = 0.15; left = 0.15;
Caxes2 = axes(‘position’, [left top width h],’FontSize’,12, …
  ‘FontName’,’Helvetica’);

plot(1:n,log10(abs(sqrt(vcl2 + vdl2) – sqrt(ccf + dcf))), …
  ‘Color’,’r’,’LineWidth’,2);
grid on;
xlabel(‘M’);
ylabel(‘Log_{10} Magnitude Error’);
xlim([2 n]);
set(gca,’XTick’,[2 50:50:n]);
print(gcf,’-depsc’,’bounderror.eps’);


END MATLAB CODE

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s