# 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.)

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