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\):

- First, is there just as simple a single-sum expression for any \(\gamma > 0\)?
- 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? - 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**