$(\mathsf{A}\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])_{i}=(2\pi\sigma^{2})^{-1}\int_{[0,6.4]^{2}}\exp\left(-\frac{1}{2\sigma^{2}}\left|\vec{x}-\Delta\begin{pmatrix}i_{1}+\tfrac{1}{2}&i_{2}+\tfrac{1}{2}\end{pmatrix}^{\top}\right|^{2}\right)\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0](\vec{x})\mathop{}\\!\mathrm{d}\vec{x},\qquad\sigma=0.2,\
\Delta=0.1$ (72)

for $i_{1},i_{2}=1,2,\ldots,64$, $\mathds{U}=\mathcal{M}([0,6.4]^{2})$ and
$\mathds{H}=L^{2}([0,6.4]^{2})$ with lengths in
$\text{\,}\mathrm{\SIUnitSymbolMicro m}$. 3020 frames are provided, examples
of which are shown in Fig. 9. To process this dataset, image intensities were
normalised to $[0,1]$ then a constant was subtracted to approximate 0-mean
noise. The greedy FISTA algorithm was used for optimisation with $\mu=0.15$,
$10^{3}$ iterations, and a maximum of $10^{5}$ pixels per image.

Finally, all the reconstructions were summed and the result shown in Fig. 11.
The adaptive scheme used fewer than $10^{4}$ pixels per frame, a fixed
discretisation with equivalent resolution of $1.3\text{\,}\mathrm{nm}$ would
have required more than $3\cdot 10^{6}$ per frame. LASSO is compared with
ThunderSTORM Ovesny2014 , a popular ImageJ plugin Schindelin2012  which finds
the location of signal using Fourier filtering. The performance of
ThunderSTORM was rated very highly in the initial SMLM challenge Sage2015 .
Both methods compared here demonstrate the key structures of the
reconstruction, however, both are sensitive to tuning parameters. In this
examples, LASSO has possibly recovered too little signal and ThunderSTORM
contains spurious signal.

Fig. 11 shows various convergence metrics for the adaptive reconstructions.
The magenta line in the first panel shows that the continuous gap converges
slightly faster than the $n^{-2/3}$ predicted by (26) in dimension $d=2$. In
this example we also implement the suggestion of Section 6.4 to remove pixels
outside of the support of $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}$. From
(56), any pixel $\omega\in\mathds{M}^{n}$ satisfying

$\IfEqCase{2}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k2]_{0}{\left\lVert\mathsf{\Pi}_{n}\mathsf{A}^{*}\vec{\varphi}_{n}\right\rVert}_{L^{\infty}(\omega)}\leq(1-\operatorname{threshold}_{n})\mu$
(73)

guarantees that
$\omega\cap\operatorname{supp}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*})=\emptyset$.
This threshold is plotted in red in the first panel of Fig. 11. Once the value
becomes less than 1, we can start reducing the number of pixels instead of
continual refinement. We see that the resolution decreases steadily (second
panel), but the total number of pixels (final panel) stops increasing after
around 30 iterations.

Figure 10: Convergence of adaptive FISTA for STORM dataset. Lines indicate the
median value over 3020 STORM frames. Shaded regions indicate the
$25\text{\,}\mathrm{\char 37\relax}75\text{\,}\mathrm{\char 37\relax}$
interquartile range. Pixel width is scaled $[0,1]$ rather than
$[0,$6.4\text{\,}\mathrm{\SIUnitSymbolMicro m}$]$.

Figure 11: Processed results of the STORM dataset. Top left: LASSO
optimisation with Algorithm 1. Top right: Comparison with ThunderSTORM plugin.
Bottom: Average data, no super-resolution or de-blurring.

##  8 Conclusions and outlook

In this work we have proposed a new adaptive variant of FISTA and provided
convergence analysis. This algorithm allows FISTA to be applied outside of the
classical Hilbert space setting, still with a guaranteed rate of convergence.
We have presented several numerical examples where convergence with the
refining discretisation is at least as fast as a uniform discretisation,
although more efficient with regards to both memory and computation time.

In 1D we see good agreement with the theoretical rate. This rate also seems to
be a good predictor for all variants of FISTA tested, although this is yet to
be proven. Even the classical methods with a fixed discretisation are
initially limited to the slower adaptive rate for small $n$.

The results in 2D are similar, all tested FISTA methods converge at least at
the guaranteed rate. The wavelet example was most impressive, achieving nearly
linear convergence in energy. This is similar to the behaviour for classical
FISTA although it is also yet to be formally proven.

An interesting observation over all of the adaptive LASSO examples is that the
standard oscillatory behaviour of FISTA has not occurred. With the monotone
gaps plotted, oscillatory convergence should correspond to a piecewise
constant descending gap. Either this behaviour only emerges for larger $n$, or
the adaptivity provides a dampening effect for this oscillation.

Moving forward, it would be interesting to see how far the analysis extends to
other optimisation algorithms. Other variants of FISTA, such as the “greedy”
implementation used here or the traditional Forward-Backward algorithm, should
also be receptive to the analysis performed here. Furthermore, it would also
interesting to attempt to replicate this refinement argument to extend the
primal-dual algorithm Chambolle2011  or the Douglas-Rachford algorithm
Douglas1956 .

###### Acknowledgements.

R.T. acknowledges funding from EPSRC grant EP/L016516/1 for the Cambridge
Centre for Analysis, and the ANR CIPRESSI project grant ANR-19-CE48-0017-01 of
the French Agence Nationale de la Recherche. Most of this work was done while
A.C. was still in CMAP, CNRS and Ecole Polytechnique, Institut Polytechnique
de Paris, Palaiseau, France. Both authors would like to thank the anonymous
reviewers who put in so much effort to improving this work.

  * Data availability statement

The synthetic STORM dataset was provided as part of the 2016 SMLM challenge,
http://bigwww.epfl.ch/smlm/challenge2016/datasets/MT4.N2.HD/Data/data.html.
The remaining examples used in this work can be generated with the
supplementary code, https://github.com/robtovey/2020SpatiallyAdaptiveFISTA.

  * Conflict of interest

The authors have no conflicts of interest to declare which are relevant to the
content of this article.

## References

  * (1) Alamo, T., Limon, D., Krupa, P.: Restart fista with global linear convergence.  In: 2019 18th European Control Conference (ECC), pp. 1969–1974. IEEE (2019)
  * (2) Aujol, J.F., Dossal, C.: Stability of over-relaxations for the forward-backward algorithm, application to fista.  SIAM Journal on Optimization 25(4), 2408–2433 (2015)
  * (3) Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM Journal on Imaging Sciences 2(1), 183–202 (2009)
  * (4) Bonnefoy, A., Emiya, V., Ralaivola, L., Gribonval, R.: Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso.  IEEE Transactions on Signal Processing 63(19), 5121–5132 (2015)
  * (5) Boyd, N., Schiebinger, G., Recht, B.: The alternating descent conditional gradient method for sparse inverse problems.  SIAM Journal on Optimization 27(2), 616–639 (2017)
  * (6) Boyer, C., Chambolle, A., Castro, Y.D., Duval, V., De Gournay, F., Weiss, P.: On representer theorems and convex regularization.  SIAM Journal on Optimization 29(2), 1260–1281 (2019)
  * (7) Bredies, K., Pikkarainen, H.K.: Inverse problems in spaces of measures.  ESAIM: Control, Optimisation and Calculus of Variations 19(1), 190–218 (2013)
  * (8) Castillo, I., Rockova, V.: Multiscale analysis of bayesian cart.  University of Chicago, Becker Friedman Institute for Economics Working Paper (2019-127) (2019)
  * (9) Catala, P., Duval, V., Peyré, G.: A low-rank approach to off-the-grid sparse superresolution.  SIAM Journal on Imaging Sciences 12(3), 1464–1500 (2019)
  * (10) Chambolle, A., Dossal, C.: On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”.  Journal of Optimization Theory and Applications 166(3), 968–982 (2015)
  * (11) Chambolle, A., Pock, T.: A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging.  Journal of Mathematical Imaging and Vision 40(1), 120–145 (2011).  DOI 10.1007/s10851-010-0251-1
  * (12) De Castro, Y., Gamboa, F., Henrion, D., Lasserre, J.B.: Exact solutions to super resolution on semi-algebraic domains in higher dimensions.  IEEE Transactions on Information Theory 63(1), 621–630 (2016)
  * (13) Denoyelle, Q., Duval, V., Peyré, G., Soubies, E.: The sliding frank–wolfe algorithm and its application to super-resolution microscopy.  Inverse Problems 36(1), 014001 (2019)
  * (14) Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables.  Transactions of the American Mathematical Society 82(2), 421–439 (1956)
  * (15) Duval, V., Peyré, G.: Sparse spikes super-resolution on thin grids i: the lasso.  Inverse Problems 33(5), 055008 (2017)
  * (16) Duval, V., Peyré, G.: Sparse spikes super-resolution on thin grids ii: the continuous basis pursuit.  Inverse Problems 33(9), 095008 (2017)
  * (17) Ekanadham, C., Tranchina, D., Simoncelli, E.P.: Recovery of sparse translation-invariant signals with continuous basis pursuit.  IEEE transactions on signal processing 59(10), 4735–4744 (2011)
  * (18) El Ghaoui, L., Viallon, V., Rabbani, T.: Safe feature elimination in sparse supervised learning.  Tech. Rep. UCB/EECS-2010–126, EECS Department, University of California, Berkeley (2010)
  * (19) Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, vol. 305.  Springer-Verlag, Berlin, Heidelberg (1993)
  * (20) Huang, J., Sun, M., Ma, J., Chi, Y.: Super-resolution image reconstruction for high-density three-dimensional single-molecule microscopy.  IEEE Transactions on Computational Imaging 3(4), 763–773 (2017)
  * (21) Jiang, K., Sun, D., Toh, K.C.: An inexact accelerated proximal gradient method for large scale linearly constrained convex sdp.  SIAM Journal on Optimization 22(3), 1042–1064 (2012)
  * (22) Kekkonen, H., Lassas, M., Saksman, E., Siltanen, S.: Random tree besov priors–towards fractal imaging.  arXiv preprint arXiv:2103.00574 (2021)
  * (23) Liang, J., Fadili, J., Peyré, G.: Activity identification and local linear convergence of forward–backward-type methods.  SIAM Journal on Optimization 27(1), 408–437 (2017)
  * (24) Liang, J., Schönlieb, C.B.: Improving fista: Faster, smarter and greedier.  arXiv preprint arXiv:1811.01430 (2018)
  * (25) Ndiaye, E., Fercoq, O., Gramfort, A., Salmon, J.: Gap safe screening rules for sparsity enforcing penalties.  The Journal of Machine Learning Research 18(1), 4671–4703 (2017)
  * (26) Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course.  Kluwer Academic Publishers Boston, Dordrecht, London (2004)
  * (27) Ovesnỳ, M., Křížek, P., Borkovec, J., Švindrych, Z., Hagen, G.M.: Thunderstorm: a comprehensive imagej plug-in for palm and storm data analysis and super-resolution imaging.  Bioinformatics 30(16), 2389–2390 (2014)
  * (28) Parpas, P.: A multilevel proximal gradient algorithm for a class of composite optimization problems.  SIAM Journal on Scientific Computing 39(5), S681–S701 (2017)
  * (29) Poon, C., Keriven, N., Peyré, G.: The geometry of off-the-grid compressed sensing.  arXiv preprint arXiv:1802.08464 (2018)
  * (30) Rosset, S., Zhu, J.: Piecewise linear regularized solution paths.  The Annals of Statistics pp. 1012–1030 (2007)
  * (31) Sage, D., Kirshner, H., Pengo, T., Stuurman, N., Min, J., Manley, S., Unser, M.: Quantitative evaluation of software packages for single-molecule localization microscopy.  Nature Methods 12(8), 717–724 (2015)
  * (32) Sage, D., Pham, T.A., Babcock, H., Lukes, T., Pengo, T., Chao, J., Velmurugan, R., Herbert, A., Agrawal, A., Colabrese, S., et al.: Super-resolution fight club: assessment of 2d and 3d single-molecule localization microscopy software.  Nature Methods 16(5), 387–395 (2019)
  * (33) Schermelleh, L., Ferrand, A., Huser, T., Eggeling, C., Sauer, M., Biehlmaier, O., Drummen, G.P.: Super-resolution microscopy demystified.  Nature cell biology 21(1), 72–84 (2019)
  * (34) Schindelin, J., Arganda-Carreras, I., Frise, E., Kaynig, V., Longair, M., Pietzsch, T., Preibisch, S., Rueden, C., Saalfeld, S., Schmid, B., et al.: Fiji: an open-source platform for biological-image analysis.  Nature Methods 9(7), 676–682 (2012)
  * (35) Schmidt, M., Roux, N.L., Bach, F.R.: Convergence rates of inexact proximal-gradient methods for convex optimization.  In: Advances in Neural Information Processing Systems, pp. 1458–1466 (2011)
  * (36) Strang, G.: Approximation in the finite element method.  Numerische Mathematik 19(1), 81–98 (1972)
  * (37) Tao, S., Boley, D., Zhang, S.: Local linear convergence of ista and fista on the lasso problem.  SIAM Journal on Optimization 26(1), 313–336 (2016)
  * (38) Unser, M., Fageot, J., Gupta, H.: Representer theorems for sparsity-promoting $\ell^{1}$ regularization.  IEEE Transactions on Information Theory 62(9), 5167–5180 (2016)
  * (39) Villa, S., Salzo, S., Baldassarre, L., Verri, A.: Accelerated and inexact forward-backward algorithms.  SIAM Journal on Optimization 23(3), 1607–1633 (2013)
  * (40) Yu, J., Lai, R., Li, W., Osher, S.: A fast proximal gradient method and convergence analysis for dynamic mean field planning.  arXiv preprint arXiv:2102.13260 (2021)

##  Appendix A Proofs for FISTA convergence

This section contains all of the statements and proofs of the results
contained in Section 4. Recall that the subsets
$\mathds{U}^{n}\subset\mathds{H}$ satisfy (10).

###  A.1 Proofs for Step 3

######  Theorem A.1 (Lemma 2)

thm: one step FISTA

$t_{n}^{2}(\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n})-\operatorname{E}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}))-(t_{n}^{2}-t_{n})(\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1})-\operatorname{E}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}))\leq\tfrac{1}{2}\left[{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1}\right\rVert}^{2}-{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}\right\rVert}^{2}\right]+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle.$
(74)

###### Proof

Modifying (Chambolle2015, , Thm 3.2), for $n\geq 1$ we apply Lemma 1 with
$\overline{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}=\overline{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}_{n-1}$
and
$\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]=(1-\frac{1}{t_{n}})\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1}+\frac{1}{t_{n}}\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}$.
By (10), $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1}\in\mathds{U}^{n}$ is
convex so $\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]\in\mathds{U}^{n}$. This gives

$\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n})+\tfrac{1}{2}{\left\lVert\tfrac{1}{t_{n}}\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\tfrac{1}{t_{n}}\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rVert}^{2}\leq\operatorname{E}\left((1-\tfrac{1}{t_{n}})\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1}+\tfrac{1}{t_{n}}\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right)+\tfrac{1}{2}{\left\lVert\tfrac{1}{t_{n}}\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1}-\tfrac{1}{t_{n}}\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rVert}^{2}.$
(75)

By the convexity of $\operatorname{E}$, this reduces to

$\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n})-\operatorname{E}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})-(1-\tfrac{1}{t_{n}})[\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1})-\operatorname{E}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})]\leq\tfrac{1}{2t_{n}^{2}}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1}-\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rVert}^{2}-\tfrac{1}{2t_{n}^{2}}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rVert}^{2}=\tfrac{1}{2t_{n}^{2}}\left[{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1}\right\rVert}^{2}-{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}\right\rVert}^{2}\right]+\tfrac{1}{t_{n}^{2}}\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle.$
(76)

Multiplying through by $t_{n}^{2}$ gives the desired inequality. ∎

######  Theorem A.2 (Theorem 4.1)

thm: mini FISTA convergence

$\Paste{thm:eq:miniFISTAconvergence}$ (77)

###### Proof

Theorem A.2 is just a summation of (74) over all $n=1,\ldots,N$. To see this:
first add and subtract
$\inf_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\mathds{H}}\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])$
to each term on the left-hand side to convert $\operatorname{E}$ to
$\operatorname{E}_{0}$, then move
$\operatorname{E}_{0}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})$ to the right-
hand side. Now (74) becomes

$t_{n}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n})-(t_{n}^{2}-t_{n})\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n-1})\leq
t_{n}\operatorname{E}_{0}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})+\tfrac{1}{2}\left[{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1}\right\rVert}^{2}-{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}\right\rVert}^{2}\right]+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle.$
(78)

Summing this inequality from $n=1$ to $n=N$ gives

$t_{N}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})+\sum_{n=1}^{N-1}(\underbrace{t_{n}^{2}-t_{n+1}^{2}+t_{n+1}}_{=\rho_{n}})\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{n})\leq\frac{{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{0}\right\rVert}^{2}-{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{N}\right\rVert}^{2}}{2}+\sum_{n=1}^{N}t_{n}\operatorname{E}_{0}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle.$
(79)

The final step is to flip the roles of
$\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}$/$\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}$
in the final inner product term. Re-writing the right-hand side gives

$\sum_{n=1}^{N}\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n}-\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle=\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{N},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{N}\right\rangle-\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{0},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{0}\right\rangle+\sum_{n=1}^{N}\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n-1}-\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle.$
(80)

Noting that
$\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{0}=\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{0}$,
the previous two equations combine to prove the statement of Theorem A.2. ∎

The following lemma is used to produce a sharper estimate on sequences
$t_{n}$.

###### Lemma 10

If $\rho_{n}=t_{n}^{2}-t_{n+1}^{2}+t_{n+1}\geq 0$, $t_{n}\geq 1$ for all
$n\in\mathds{N}$ then $t_{n}\leq n-1+t_{1}$.

###### Proof

This is trivially true for $n=1$. Suppose true for $n-1$, the condition on
$\rho_{n-1}$ gives

$t_{n}^{2}-t_{n}\leq
t_{n-1}^{2}\leq(n-2+t_{1})^{2}=(n-1+t_{1})^{2}-2(n-1+t_{1})+1.$ (81)

Assuming the contradiction, if $t_{n}>n-1+t_{1}$ then the above equation
simplifies to $n-1+t_{1}<1$. However, $t_{1}\geq 1$ implying that $n<1$ which
completes the contradiction. ∎

######  Lemma 11 (Lemma 3)

thm: mini exponential FISTA convergence

$\Paste{thm:eq:miniexponentialFISTAconvergence}$ (82)

thm:end: mini exponential FISTA convergence

###### Proof

This is just a telescoping of the right-hand side of (77) with the
introduction of $n_{k}$ and simplification
$\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}=\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}$,

$\tfrac{1}{2}{\left\lVert\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{N}\right\rVert}^{2}+\sum^{N}_{n=1}t_{n}\operatorname{E}_{0}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n})+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n-1},\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n-1}-\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]_{n}\right\rangle=\tfrac{1}{2}{\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}+\sum_{n=n_{K}}^{N}t_{n}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K})+\sum_{k=1}^{K}\sum_{n=n_{k-1}}^{n_{k}-1}t_{n}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1})+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1},\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right\rangle.$
(83)

By Lemma 10, $t_{n}\leq n$ so we can further simplify

$\sum_{n=\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}^{\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]-1}t_{n}\leq\sum_{n=\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}^{\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]-1}n=(\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]-\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3])\frac{\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]-1+\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}{2}\leq\frac{\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]^{2}-\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]^{2}}{2}$

to get the required bound. ∎

###  A.2 Proof for Step 4

######  Lemma 12 (Lemma 4)

thm: sufficiently fast

###### Proof

Starting from Lemma 11 we have

$\displaystyle
t_{N}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})+\tfrac{1}{2}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{N}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}$
$\displaystyle\leq
C+\frac{{\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}}{2}+\frac{(N+1)^{2}-n_{K}^{2}}{2}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K})$
$\displaystyle\hskip
70.0pt+\sum_{k=1}^{K}\frac{n_{k}^{2}-n_{k-1}^{2}}{2}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1})+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1},\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k+1}\right\rangle$
(84) $\displaystyle\leq
C+\frac{{\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}}{2}+\frac{n_{K+1}^{2}}{2}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K})$
$\displaystyle\hskip
40.0pt+\sum_{k=1}^{K}\frac{n_{k}^{2}}{2}\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1})+\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}+\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1},{\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}}\right\rangle.$
(85)

The inductive step now depends on the value of $a_{\operatorname{U}}$.

Case $a_{\operatorname{U}}>1$:

We simplify the inequality

$\displaystyle
t_{N}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})+\tfrac{1}{2}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{N}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}$
$\displaystyle\lesssim
a_{\operatorname{U}}^{2K}+n_{K+1}^{2}a_{\operatorname{E}}^{-K}+\sum_{k=1}^{K}n_{k}^{2}a_{\operatorname{E}}^{-k}+a_{\operatorname{U}}^{k}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}+a_{\operatorname{U}}^{2k}$
(86) $\displaystyle\leq
C_{1}\left[a_{\operatorname{U}}^{2K+2}+\sum_{k=1}^{K}a_{\operatorname{U}}^{2k}+a_{\operatorname{U}}^{k}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\right]$
(87)

for some $C_{1}>C$. Choose
$C_{2}\geq{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{1}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{1-1}\right\rVert}a_{\operatorname{U}}^{-1}$
such that

$\frac{1}{2}C_{2}^{2}\geq\frac{C_{1}}{a_{\operatorname{U}}^{2}-1}(C_{2}+a_{\operatorname{U}}^{2}).$
(88)

Assume
${\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\leq
C_{2}a_{\operatorname{U}}^{k}$ for $1\leq k\leq K$ (trivially true for $K=1$),
then for $N=n_{K+1}-1$ we have

$\displaystyle\tfrac{1}{2}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{K+1}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}$
$\displaystyle\leq
C_{1}\left[a_{\operatorname{U}}^{2K+2}+\sum_{k=1}^{K}a_{\operatorname{U}}^{2k}+a_{\operatorname{U}}^{k}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\right]$
(89) $\displaystyle\leq
C_{1}\left[a_{\operatorname{U}}^{2K+2}+(1+C_{2})\frac{a_{\operatorname{U}}^{2K+2}}{a_{\operatorname{U}}^{2}-1}\right]$
(90)
$\displaystyle\leq\frac{C_{1}a_{\operatorname{U}}^{2K+2}}{a_{\operatorname{U}}^{2}-1}\left(a_{\operatorname{U}}^{2}+C_{2}\right)\leq\tfrac{1}{2}(C_{2}a_{\operatorname{U}}^{K+1})^{2}.$
(91)

Case $a_{\operatorname{U}}=1$:

Denote
$\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k}={\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k+1}\right\rVert}$
and note that
${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\leq{\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{0}\right\rVert}+\sum_{0}^{\infty}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k}\lesssim
1$. We therefore bound

$\displaystyle
t_{N}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})+\tfrac{1}{2}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{N}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}$
$\displaystyle\lesssim
1+n_{K+1}^{2}a_{\operatorname{E}}^{-K}+\sum_{k=1}^{K}n_{k}^{2}a_{\operatorname{E}}^{-k}+({\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}+1)b_{k}$
(92) $\displaystyle\leq
C_{1}\left[1+\sum_{k=1}^{K}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k-1}\right]$
(93)

for some $C_{1}>0$. Choose
$C_{2}\geq\frac{{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{1}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{1-1}\right\rVert}}{\sum_{0}^{\infty}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k}}$
such that

$\frac{1}{2}C_{2}^{2}\geq
C_{1}\left(1+C_{2}\sum_{0}^{\infty}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k}\right).$
(94)

Assume
${\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\leq
C_{2}$ for $1\leq k\leq K$ (trivially true for $K=1$), then for $N=n_{K+1}-1$
we have

$\tfrac{1}{2}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{K+1}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}^{2}\leq
C_{1}\left[1+\sum_{k=1}^{K}{\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{k}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1}\right\rVert}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k-1}\right]\leq
C_{1}\left(1+C_{2}\sum_{0}^{\infty}\IfEqCase{4}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k4]_{k}\right)\leq\frac{C_{2}^{2}}{2}$
(95)

In both cases, the induction on
${\left\lVert\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]_{n_{K+1}-1}-\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{K}\right\rVert}$
holds for all $K$, and we have
$t_{N}^{2}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})\leq\frac{1}{2}C_{2}^{2}a_{\operatorname{U}}^{2K}$
for all $N<n_{K}-1$. ∎

###  A.3 Proof for Step 5

######  Lemma 13 (Lemma 5)

thm: sufficiently slow

###### Proof

The proof is direct computation, note that

$(a_{\operatorname{E}}a_{\operatorname{U}}^{2})^{\kappa}=\exp\left(\kappa\log(a_{\operatorname{E}}a_{\operatorname{U}}^{2})\right)=\exp(\log
a_{\operatorname{U}}^{2})=a_{\operatorname{U}}^{2},$ (96)

therefore

$a_{\operatorname{U}}^{2K}=\left((a_{\operatorname{E}}a_{\operatorname{U}}^{2})^{K}\right)^{\kappa}\lesssim
n_{K}^{2\kappa}\leq N^{2\kappa},$ (97)

so $\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})\lesssim
N^{-2(1-\kappa)}$ as required. ∎

###  A.4 Proofs for Step 6

######  Theorem A.3 (Theorem 4.3)

thm: stronger exponential FISTA convergence

###### Proof

Let $C>0$ satisfy $n_{k}^{2}\leq
Ca_{\operatorname{E}}^{k}a_{\operatorname{U}}^{2k}$ for each $k\in\mathds{N}$.
Fix $N>C$ and choose $k$ such that
$Ca_{\operatorname{E}}^{k-1}a_{\operatorname{U}}^{2k-2}\leq
N<Ca_{\operatorname{E}}^{k}a_{\operatorname{U}}^{2k}$. By construction, and
using the equality from (96), we have

$\min_{n\leq
N}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]_{N})\leq\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k-1})\lesssim
a_{\operatorname{E}}^{-k}=(a_{\operatorname{E}}a_{\operatorname{U}}^{2})^{-k(1-\kappa)}<C^{\kappa-1}N^{-2(1-\kappa)}$
(98)

as required. ∎

######  Lemma 14 (Lemma 6)

thm: practical refinement criteria

###### Proof

The conditions for $a_{\operatorname{U}}$ in Definition 1 are already met, it
remains to be shown that
$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})\leq
Ca_{\operatorname{E}}^{-k}$ for some fixed $C>0$. For cases (3) and (4), fix
$R>0$ such that both
$\\{\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\\}_{k\in\mathds{N}}$
and the sublevel set
$\\{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\mathds{U}\operatorname{\;s.t.\;}\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])\leq
1+\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]\\}$ are
contained in the ball of radius $R$. Any minimising sequences of
$\operatorname{E}$ in $\mathds{U}$ or $\widetilde{\mathds{U}}^{k}$ are
contained in this ball. We can therefore compute $C$ in each case:

  * (1)

$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})\leq\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]a_{\operatorname{E}}^{-k}$,
so $C=\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]$
suffices.

  * (2)

$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})\leq\operatorname{E}_{0}(\widetilde{\mathds{U}}^{k})+\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]a_{\operatorname{E}}^{-k}\leq(a_{\operatorname{E}}+1)\beta
a_{\operatorname{E}}^{-k}$, so $C=(a_{\operatorname{E}}+1)\beta$ suffices.

  * (3)

$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])\leq\inf_{\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]\in\partial\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})}\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1],\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rangle\leq
2R\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]a_{\operatorname{E}}^{-k}$
for any $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\mathds{U}$ with
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
R$. Maximising over $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]$ gives
$C=2R\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]$

  * (4)

$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}_{0}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])\leq\inf_{\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1]\in\partial\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})}\left\langle\IfEqCase{1}{{0}{u}{1}{v}{2}{w}}[u1],\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rangle\leq
2R\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]a_{\operatorname{E}}^{-k}$
for any $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}^{k}$
with
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
R$, so
$\operatorname{E}_{0}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})\leq\operatorname{E}_{0}(\widetilde{\mathds{U}}^{k})+2R\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]a_{\operatorname{E}}^{-k}$
and
$C=(1+2R)\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]$.

This completes the requirements of Definition 1. ∎

##  Appendix B Proof of Theorem 5.1

First we recall the setting of Definition 2, fix: $p\geq 0$, $q\in[1,\infty]$,
$h\in(0,1)$, $N\in\mathds{N}$, connected and bounded domain
$\Omega\subset\mathds{R}^{d}$, and
$\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\in\operatorname*{argmin}_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\mathds{U}}\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0])$.
We assume that $\mathds{H}=L^{2}(\Omega)$,
${\left\lVert\cdot\right\rVert}_{q}\lesssim{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$,
and there exist spaces $(\widetilde{\mathds{U}}^{k})_{k\in\mathds{N}}$ with
$\widetilde{\mathds{U}}^{k}\subset\mathds{U}$ containing a sequence
$(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\in\widetilde{\mathds{U}}^{k})_{k\in\mathds{N}}$
such that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\lesssim
h^{kp}$, c.f. (16). Furthermore, there exists constant $c_{\alpha}>0$ and
meshes $\mathds{M}^{k}$ such that:

$\displaystyle\exists\omega_{0}\subset\Omega\quad\text{such
that}\quad\forall\omega\in\mathds{M}^{k}\quad\exists(\IfEqCase{0}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k0]_{\omega},\vec{\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]}_{\omega})\in\mathds{R}^{d\times
d}\times\mathds{R}^{d}\quad\text{such
that}\quad\vec{x}\in\omega_{0}\iff\IfEqCase{0}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k0]_{\omega}\vec{x}+\vec{\IfEqCase{1}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k1]}_{\omega}\in\omega,\qquad\text{
and}$ (99)
$\displaystyle\forall(\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]},\omega)\in\widetilde{\mathds{U}}^{k}\times\mathds{M}^{k},\quad\exists\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}^{0}\quad\text{such
that}\quad\operatorname{det}(\alpha_{\omega})\geq
c_{\alpha}h^{kd}\quad\text{and}\quad\forall\vec{x}\in\omega_{0},\
\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0](\vec{x})=\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}(\alpha_{\omega}\vec{x}+\vec{\beta}_{\omega}).$
(100)

In this section, these assumptions will be summarised simply by saying that
$\mathds{H}$ and $(\widetilde{\mathds{U}}^{k})_{k\in\mathds{N}}$ satisfy
Definition 2. We prove Theorem 5.1 as a consequence of Lemma 7, namely we
compute exponents $p^{\prime},q^{\prime}$ with
$a_{\operatorname{U}}=h^{-q^{\prime}}$ and
$a_{\operatorname{E}}=h^{-p^{\prime}}$. These values are computed as the
result of the following three lemmas. The first, Lemma 15, is a quantification
of the equivalence between $L^{q}$ and $L^{2}$ norms on general sub-spaces.
Lemma 16 applies this result to finite-element spaces to compute the value of
$q^{\prime}$. Finally, Lemma 17 then performs the computations for
$p^{\prime}$ depending on the smoothness properties of $\operatorname{E}$.

######  Lemma 15 (Equivalence of norms for fixed $k$)

Suppose $\mathds{H}=L^{2}(\Omega)$ for some connected, bounded domain
$\Omega\subset\mathds{R}^{d}$ and ${\left\lVert\cdot\right\rVert}_{q}\leq
C{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
for some $q\in[1,\infty]$, $C>0$. For any linear subspace
$\widetilde{\mathds{U}}\subset\mathds{U}$ and
$\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\in\widetilde{\mathds{U}}$,

${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right\rVert}\leq\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}}\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\quad\text{where}\quad\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}}\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}\leq
C^{-1}\begin{cases}|\Omega|^{\frac{1}{2}-\frac{1}{q}}&\text{ if }q\geq
2\text{, otherwise}\\\
|\Omega|^{1-\frac{1}{q}}\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}}{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{\infty}/{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\qquad&\text{
if }q\in[1,2).\end{cases}$ (101)

###### Proof

The first statement of the result is by definition, for each
$\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\in\widetilde{\mathds{U}}\subset
L^{\infty}(\Omega)\subset\mathds{H}$ we have

${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right\rVert}=\frac{\left\langle\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]},\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right\rangle}{{\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right\rVert}}\leq\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}}\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}}\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}.$

Recall
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\geq
C^{-1}{\left\lVert\cdot\right\rVert}_{q}$. To go further we use Hölder’s
inequality. If $\frac{1}{q}+\frac{1}{q^{*}}=1$, then for any
$\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}$

$\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}\leq
C^{-1}\frac{\left\langle\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0],\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rangle}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\,{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{q}}\leq
C^{-1}\frac{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{q^{*}}}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}}.$
(102)

If $q\geq 2$ we use Hölder’s inequality a second time:

$\int_{\Omega}|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0](\vec{x})|^{q^{*}}\mathop{}\\!\mathrm{d}\vec{x}\leq\left(\int_{\Omega}1\mathop{}\\!\mathrm{d}\vec{x}\right)^{1-q^{*}/2}\left(\int_{\Omega}|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0](\vec{x})|^{2}\mathop{}\\!\mathrm{d}\vec{x}\right)^{q^{*}/2}=\left(|\Omega|^{\frac{1}{2}-\frac{1}{q}}{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}\right)^{q^{*}}.$
(103)

This confirms the inequality when $q\geq 2$. If $q<2$, we can simply upper
bound
${\left\lVert\cdot\right\rVert}_{q^{*}}\leq|\Omega|^{\frac{1}{q^{*}}}{\left\lVert\cdot\right\rVert}_{\infty}$
as required. ∎

###### Lemma 16

Suppose $\mathds{H}$ and $(\widetilde{\mathds{U}}^{k})_{k\in\mathds{N}}$
satisfy Definition 2, then

  1. 1.

If $q\geq 2$, then
${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right\rVert}\lesssim
1$ (i.e. $q^{\prime}=0$).

  2. 2.

If $q<2$ and
$\sup_{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}^{0}}\frac{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{\infty}(\omega_{0})}}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{2}(\omega_{0})}}<\infty$,
then
${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right\rVert}\lesssim
h^{-\frac{kd}{2}}$ (i.e. $q^{\prime}=-\frac{d}{2}$).

###### Proof

Most of the conditions of Lemma 15 are already satisfied. Furthermore observe
that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\lesssim{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}+h^{kp}\lesssim
1$. For the $q\geq 2$ case, this is already sufficient to conclude
${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right\rVert}\lesssim
1$ from Lemma 15, as required.

For the case $q<2$, from Lemma 15 recall that we are required to bound

$\sup_{\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}^{k}}\frac{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{\infty}}{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}}=\sup_{\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}^{k}}\sup_{\omega\in\mathds{M}^{k}}\frac{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{\infty}(\omega)}}{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{2}(\Omega)}}\leq\sup_{\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}^{k}}\sup_{\omega\in\mathds{M}^{k}}\frac{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{\infty}(\omega)}}{{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{2}(\omega)}}.$
(104)

However, due to the decomposition property (100), for each
$\omega\in\mathds{M}^{k}$ and
$\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\in\widetilde{\mathds{U}}^{k}$
there exists
$\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\in\widetilde{\mathds{U}}^{0}$ such that

${\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{\infty}(\omega_{0})}={\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{\infty}(\omega)},\qquad{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{2}(\omega_{0})}^{2}=\int_{\omega_{0}}|\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0](\vec{x})|^{2}\mathop{}\\!\mathrm{d}\vec{x}=\int_{\omega_{0}}|\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}(\alpha\vec{x}+\vec{\beta})|^{2}\mathop{}\\!\mathrm{d}\vec{x}=\operatorname{det}(\alpha)^{-1}{\left\lVert\widetilde{\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]}\right\rVert}_{L^{2}(\omega)}^{2}.$
(105)

Combining these two equations with the assumed bound on
$\frac{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{\infty}(\omega_{0})}}{{\left\lVert\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]\right\rVert}_{L^{2}(\omega_{0})}}$
confirms
${\left\lVert\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}\right\rVert}\lesssim\sqrt{\operatorname{det}(\alpha)^{-1}}\leq
c_{\alpha}^{-\frac{1}{2}}h^{-\frac{kd}{2}}$ as required. ∎

###### Lemma 17

Suppose $\mathds{H}$ and $(\widetilde{\mathds{U}}^{k})_{k\in\mathds{N}}$
satisfy Definition 2 and $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}$ is the
minimiser of $E$ such that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\lesssim
h^{kp}$.

  1. 1.

If $\operatorname{E}$ is
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$-Lipschitz
at $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}$, then
$\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*})\lesssim
h^{kp}$ (i.e. $p^{\prime}=p$).

  2. 2.

If $\nabla\operatorname{E}$ is
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$-Lipschitz
at $\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}$, then
$\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*})\lesssim
h^{2kp}$ (i.e. $p^{\prime}=2p$).

###### Proof

Both statements are direct by definition, observe

$\displaystyle\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*})\leq\operatorname{Lip}(\operatorname{E}){\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|},$
(106)
$\displaystyle\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*})\leq\left\langle\nabla\operatorname{E}(\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]),\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right\rangle=\left\langle\nabla\operatorname{E}(\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k})-\nabla\operatorname{E}(\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}),\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right\rangle\leq\operatorname{Lip}(\nabla\operatorname{E}){\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}-\IfEqCase{0}{{0}{u}{1}{v}{2}{w}}[u0]^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}.$
(107)

The proof is concluded by using the approximation bounds of
$\widetilde{\IfEqCase{2}{{0}{u}{1}{v}{2}{w}}[u2]}_{k}$ in Definition 2. ∎

##  Appendix C Operator norms for numerical examples

###### Theorem C.1

Suppose $\mathsf{A}\colon\mathds{H}\to\mathds{R}^{m}$ has kernels $\psi_{j}\in
L^{\infty}([0,1]^{d})$ for $j\in[m]$.

  1. Case 1:

If $\psi_{j}(\vec{x})=\begin{cases}1&\vec{x}\in\mathds{X}_{j}\\\ 0&\text{
else}\end{cases}$ for some collection $\mathds{X}_{j}\subset\Omega$ such that
$\mathds{X}_{i}\cap\mathds{X}_{j}=\emptyset$ for all $i\neq j$, then
${\left\lVert\mathsf{A}\right\rVert}_{L^{2}\to\ell^{2}}=\max_{j\in[m]}\sqrt{|\mathds{X}_{j}|}.$

  2. Case 2:

If
$\psi_{j}(\vec{x})=\cos(\vec{\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}_{j}\vbox{\hbox{\leavevmode\resizebox{6.0pt}{}{$\cdot$}}}\vec{x})$
for some frequencies
$\vec{\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}_{j}\in\mathds{R}^{d}$
with
$|\vec{\IfEqCase{3}{{0}{\alpha}{1}{\beta}{2}{\gamma}{3}{a}{4}{b}{5}{c}}[k3]}_{j}|\leq
A$, then

${\left\lVert\mathsf{A}\right\rVert}_{L^{2}\to\ell^{2}}\leq\sqrt{m},\qquad|\mathsf{A}^{*}\vec{r}|_{C^{k}}\leq
m^{1-\frac{1}{q}}A^{k}{\left\lVert\vec{r}\right\rVert}_{q},\quad\text{and}\quad|\mathsf{A}^{*}|_{\ell^{2}\to
C^{k}}\leq\sqrt{m}A^{k}$

for all $\vec{r}\in\mathds{R}^{m}$ and $q\in[1,\infty]$.

  3. Case 3:

Suppose
$\psi_{j}(\vec{x})=(2\pi\sigma^{2})^{-\frac{d}{2}}\exp\left(-\frac{|\vec{x}-\vec{x}_{j}|^{2}}{2\sigma^{2}}\right)$
for some regular mesh $\vec{x}_{j}\in[0,1]^{d}$ and separation $\Delta$. i.e.

$\\{\vec{x}_{j}\operatorname{\;s.t.\;}j\in[m]\\}=\\{\vec{x}_{0}+(j_{1}\Delta,\ldots,j_{d}\Delta)\operatorname{\;s.t.\;}j_{i}\in[\widehat{m}]\\}$

for some $\vec{x}_{0}\in\mathds{R}^{d}$, $\widehat{m}\coloneqq\sqrt[d]{m}$.
For all $\frac{1}{q}+\frac{1}{q^{*}}=1$, $q\in(1,\infty]$, we have

$\displaystyle{\left\lVert\mathsf{A}\right\rVert}_{L^{2}\to\ell^{2}}$
$\displaystyle\leq\bigg{(}(4\pi\sigma^{2})^{-\frac{1}{2}}\sum_{j=-2\widehat{m},\ldots,2\widehat{m}}\exp(-\tfrac{\Delta^{2}}{4\sigma^{2}}j^{2})\bigg{)}^{d},$
(108) $\displaystyle|\mathsf{A}^{*}\vec{r}|_{C^{0}}$
$\displaystyle\leq(2\pi\sigma^{2})^{-\frac{d}{2}}\bigg{(}\sum_{\vec{j}\in
J}\exp\left(-\tfrac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\bigg{)}^{\frac{1}{q^{*}}}{\left\lVert\vec{r}\right\rVert}_{q},$
(109) $\displaystyle|\mathsf{A}^{*}\vec{r}|_{C^{1}}$
$\displaystyle\leq\frac{(2\pi\sigma^{2})^{-\frac{d}{2}}}{\sigma}\frac{\Delta}{\sigma}\bigg{(}\sum_{\vec{j}\in
J}(|\vec{j}|+\delta)^{q^{*}}\exp\left(-\tfrac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\bigg{)}^{\frac{1}{q^{*}}}{\left\lVert\vec{r}\right\rVert}_{q},$
(110) $\displaystyle|\mathsf{A}^{*}\vec{r}|_{C^{2}}$
$\displaystyle\leq\frac{(2\pi\sigma^{2})^{-\frac{d}{2}}}{\sigma^{2}}\bigg{(}\sum_{\vec{j}\in
J}\left(1+\tfrac{\Delta^{2}}{\sigma^{2}}(|\vec{j}|+\delta)^{2}\right)^{q^{*}}\exp\left(-\tfrac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\bigg{)}^{\frac{1}{q^{*}}}{\left\lVert\vec{r}\right\rVert}_{q},$
(111)

where $\delta=\frac{\sqrt{d}}{2}$ and
$J=\\{\vec{j}\in\mathds{Z}^{d}\operatorname{\;s.t.\;}{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
2\widehat{m}\\}$. The case for $q=1$ can be inferred from the standard limit
of
${\left\lVert\cdot\right\rVert}_{{q^{*}}}\to{\left\lVert\cdot\right\rVert}_{\infty}$
for $q^{*}\to\infty$.

######  Proof (Case 1.)

From Lemma 8 we have

$(\mathsf{A}\mathsf{A}^{*})_{i,j}=\left\langle\mathds{1}_{\mathds{X}_{i}},\mathds{1}_{\mathds{X}_{j}}\right\rangle=|\mathds{X}_{i}\cap\mathds{X}_{j}|=\begin{cases}|\mathds{X}_{i}|&i=j\\\
0&i\neq j\end{cases}.$ (112)

Therefore, $\mathsf{A}\mathsf{A}^{*}$ is a diagonal matrix and
${\left\lVert\mathsf{A}\mathsf{A}^{*}\right\rVert}_{\ell^{2}\to\ell^{2}}=\max_{j\in[m]}|\mathds{X}_{j}|$
completes the result. ∎

######  Proof (Case 2.)

$\psi_{j}$ are not necessarily orthogonal however
$|\left\langle\psi_{i},\psi_{j}\right\rangle|\leq 1$ therefore we can estimate

${\left\lVert\mathsf{A}\mathsf{A}^{*}\right\rVert}_{\ell^{2}\to\ell^{2}}\leq{\left\lVert\mathsf{A}\mathsf{A}^{*}\right\rVert}_{\ell^{\infty}\to\ell^{\infty}}\leq
m.$ (113)

Now looking to apply Lemma 9, note
${\left\lVert\nabla^{k}\psi_{j}\right\rVert}_{\infty}\leq A^{k}$, therefore

$|\mathsf{A}^{*}\vec{r}|_{C^{k}}\leq
A^{k}m^{\frac{1}{q^{*}}}{\left\lVert\vec{r}\right\rVert}_{q}=A^{k}m^{1-\frac{1}{q}}{\left\lVert\vec{r}\right\rVert}_{q}\quad\text{and}\quad|\mathsf{A}^{*}|_{\ell^{2}\to
C^{k}}\leq
A^{k}\min_{q\in[1,\infty]}m^{1-\frac{1}{q}}\sqrt{m}^{\max(0,2-q)}=\sqrt{m}A^{k}.$
(114)

∎

######  Proof (Case 3.)

In the Gaussian case, we build our approximations around the idea that sums of
Gaussians should converge very quickly. The first example can be used to
approximate the operator norm. Computing the inner products gives

$\left\langle\psi_{i},\psi_{j}\right\rangle=(2\pi\sigma^{2})^{-d}\int_{[0,1]^{d}}\exp\left(-\tfrac{|\vec{x}-\vec{x}_{i}|^{2}}{2\sigma^{2}}-\tfrac{|\vec{x}-\vec{x}_{j}|^{2}}{2\sigma^{2}}\right)\mathop{}\\!\mathrm{d}\vec{x}\leq(2\pi\sigma^{2})^{-d}(\pi\sigma^{2})^{\frac{d}{2}}\exp\left(-\tfrac{|\vec{x}_{i}-\vec{x}_{j}|^{2}}{4\sigma^{2}}\right).$
(115)

Estimating the operator norm,

$\displaystyle{\left\lVert\mathsf{A}\mathsf{A}^{*}\right\rVert}_{\ell^{2}\to\ell^{2}}$
$\displaystyle\leq{\left\lVert\mathsf{A}\mathsf{A}^{*}\right\rVert}_{\ell^{\infty}\to\ell^{\infty}}=\max_{i\in[m]}\sum_{j=1}^{m}|\left\langle\psi_{i},\psi_{j}\right\rangle|$
(116)
$\displaystyle=\max_{i\in[m]}(4\pi\sigma^{2})^{-\frac{d}{2}}\sum_{j_{1},\ldots,j_{d}\in[\widehat{m}]}\exp\left(-\frac{(j_{1}\Delta-
i_{1}\Delta)^{2}+\ldots+(j_{d}\Delta-i_{d}\Delta)^{2}}{4\sigma^{2}}\right)$
(117)
$\displaystyle\leq(4\pi\sigma^{2})^{-\frac{d}{2}}\sum_{\vec{j}\in\mathds{Z}^{d}\cap[-\widehat{m},\widehat{m}]^{d}}\exp\left(-\frac{(j_{1}\Delta)^{2}+\ldots+(j_{d}\Delta)^{2}}{4\sigma^{2}}\right)=\left[(4\pi\sigma^{2})^{-\frac{1}{2}}\sum_{j=-\widehat{m}}^{\widehat{m}}\exp\left(-\frac{\Delta^{2}j^{2}}{4\sigma^{2}}\right)\right]^{d}.$
(118)

This is a nice approximation because it factorises simply over dimensions.
Applying the results from Lemma 9, note

$\begin{array}[]{rll}\displaystyle|\psi_{j}(\vec{x})|&\displaystyle=\left|\psi_{j}(\vec{x})\right|&\displaystyle=(2\pi\sigma^{2})^{-\frac{d}{2}}\exp\left(-\frac{|\vec{x}-\vec{x}_{j}|^{2}}{2\sigma^{2}}\right),\\\
\displaystyle|\nabla\psi_{j}(\vec{x})|&\displaystyle=\left|\frac{\vec{x}-\vec{x}_{j}}{\sigma^{2}}\psi_{j}(\vec{x})\right|&\displaystyle=\frac{(2\pi\sigma^{2})^{-\frac{d}{2}}}{\sigma}\frac{|\vec{x}-\vec{x}_{j}|}{\sigma}\exp\left(-\frac{|\vec{x}-\vec{x}_{j}|^{2}}{2\sigma^{2}}\right),\\\
|\nabla^{2}\psi_{j}(\vec{x})|&\displaystyle=\left|\frac{1}{\sigma^{2}}+\frac{(\vec{x}-\vec{x}_{j})(\vec{x}-\vec{x}_{j})^{\top}}{\sigma^{4}}\right|\psi_{j}(\vec{x})&\displaystyle=\frac{(2\pi\sigma^{2})^{-\frac{d}{2}}}{\sigma^{2}}\left(1+\frac{|\vec{x}-\vec{x}_{j}|^{2}}{\sigma^{2}}\right)\exp\left(-\frac{|\vec{x}-\vec{x}_{j}|^{2}}{2\sigma^{2}}\right).\end{array}$

We now wish to sum over $j=1,\ldots,m$ and produce an upper bound on these,
independent of $t$. To do so we will use the following lemma.

###### Lemma 18

Suppose $q>0$. If the polynomial $p(|\vec{x}|)=\sum p_{k}|\vec{x}|^{k}$ has
non-negative coefficients and $\vec{x}\in[-m,m]^{d}$, then

$\sum_{{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
m}p(|\vec{j}-\vec{x}|)\exp\left(-\tfrac{q|\vec{j}-\vec{x}|^{2}}{2}\right)\leq\sum_{{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
2m}p(|\vec{j}|+\delta)\exp\left(-\frac{q\max(0,|\vec{j}|-\delta)^{2}}{2}\right)$

where $\delta\coloneqq\frac{\sqrt{d}}{2}$ and $\vec{j}\in\mathds{Z}^{d}$.

###### Proof

There exists $\widehat{\vec{x}}\in[-\tfrac{1}{2},\tfrac{1}{2}]^{d}$ such that
$\vec{x}+\widehat{\vec{x}}\in\mathds{Z}^{d}$, therefore

$\displaystyle\sum_{{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
m}p(|\vec{j}-\vec{x}|)\exp\left(-\tfrac{q|\vec{j}-\vec{x}|^{2}}{2}\right)$
$\displaystyle=\sum_{{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
m}p(|\vec{j}-(\vec{x}+\widehat{\vec{x}})+\widehat{\vec{x}}|)\exp\left(-\tfrac{q|\vec{j}-(\vec{x}+\widehat{\vec{x}})+\widehat{\vec{x}}|^{2}}{2}\right)$
$\displaystyle\leq\sum_{{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
2m}p(|\vec{j}+\widehat{\vec{x}}|)\exp\left(-\tfrac{q|\vec{j}+\widehat{\vec{x}}|^{2}}{2}\right)$
$\displaystyle\leq\sum_{\begin{subarray}{c}\vec{j}\in\mathds{Z}^{d}\\\
{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
2m\end{subarray}}p(|\vec{j}|+\delta)\exp\left(-\tfrac{q\max(0,|\vec{j}|-\delta)^{2}}{2}\right)$

as $|\widehat{\vec{x}}|\leq\delta$ and $p$ has non-negative coefficients. ∎

Now, continuing the proof of Theorem C.1, for $\widehat{m}=\sqrt[d]{m}$,
$\delta=\frac{\sqrt{d}}{2}$ and
$J=\\{\vec{j}\in\mathds{Z}^{d}\operatorname{\;s.t.\;}{\left\lVert\vec{j}\right\rVert}_{\ell^{\infty}}\leq
2\widehat{m}\\}$, Lemma 18 bounds

$\displaystyle\sum_{j=1}^{m}|\psi_{j}(\vec{x})|^{q^{*}}$
$\displaystyle\leq(2\pi\sigma^{2})^{-\frac{dq^{*}}{2}}\left[\sum_{\vec{j}\in
J}\exp\left(-\frac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\right]$
$\displaystyle\sum_{j=1}^{m}|\nabla\psi_{j}(\vec{x})|^{q^{*}}$
$\displaystyle\leq\frac{(2\pi\sigma^{2})^{-\frac{dq^{*}}{2}}}{\sigma^{q^{*}}}\frac{\Delta^{q^{*}}}{\sigma^{q^{*}}}\left[\sum_{\vec{j}\in
J}(|\vec{j}|+\delta)^{q^{*}}\exp\left(-\frac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\right]$
$\displaystyle\sum_{j=1}^{m}|\nabla^{2}\psi_{j}(\vec{x})|^{q^{*}}$
$\displaystyle\leq\frac{(2\pi\sigma^{2})^{-\frac{dq^{*}}{2}}}{\sigma^{2q^{*}}}\left[\sum_{\vec{j}\in
J}\left(1+\frac{\Delta^{2}}{\sigma^{2}}(|\vec{j}|+\delta)^{2}\right)^{q^{*}}\exp\left(-\frac{q^{*}\Delta^{2}}{2\sigma^{2}}\max(0,|\vec{j}|-\delta)^{2}\right)\right]$

for all $\vec{x}\in\Omega$. In a worst case, this is $O(2^{d}m)$ time
complexity however the summands all decay faster than exponentially and so
should converge very quickly. ∎