# Appendix B Efficient Wavelet-Based Reconstruction

## B.1 Proof of Proposition 1

**Proof.**
We rewrite the cost function (2) with the change of variable **w**′ = **Λ**^{1/2}**w**. We then apply ISTA to solve the problem in terms of **w**′. The new parameters are **a**′ = **Λ**^{−1/2}**a**, **A**′=**Λ**^{−1/2}**AΛ**^{−1/2}, and thresholds λ√τ_{k} that are specific to each coefficient. Noting that **Λ**−**A** is positive-definite if and only if **I** −**A**′ is positive-definite leads us to *L* = 2. The iteration **w**_{i+1}′=T_{λ√τ}(**w**_{i}′+(**a**′−**A**′**w**_{i}′)) can be rewritten, in terms of the original variable, as **w**_{i+1}=T_{λτ}(**w**_{i}+**Λ**^{−1}(**a**−**Aw**_{i})). The latter is nothing but an iteration of SISTA (see Algorithm 1). According to Proposition 1, we have *C*(**Λ**^{−1/2}**w**_{i}′)− *C*(**w**^{⋆})≤ ||**w**_{i0}′−**Λ**^{1/2}**w**^{⋆} ||^{2}/(*i*−*i*_{0}), which translates directly into the proposed result.

## B.2 Proof of Proposition 2

**Proof.**
In the spirit of the proof of Proposition 1, we consider the change of variable **w**′ = **Λ**^{1/2}**w** and apply FISTA to solve the new reconstruction problem. The ISTA step **w**_{i+1}′ = T_{λ√τ}(**v**_{i}′+(**a**′−**A**′**v**_{i}′)) is equivalent to a SISTA step in terms of the original variable **w**_{i+1} = T_{λτ}(**v**_{i}+**Λ**^{−1}(**a**−**Av**_{i})). The convergence results of FISTA [20, Thm. 4.4] applies on the sequence {**w**_{i}′}, which leads to *C*(**Λ**^{−1/2}**w**_{i}′)− *C*(**w**^{⋆})≤ 4/(*i*+1)^{2}||**w**_{0}′−**Λ**^{1/2}**w**^{⋆} ||^{2}.
In the strongly convex case, we have

| ⎪⎪
⎪⎪ | **w**_{i}−**w**^{⋆} | ⎪⎪
⎪⎪ | _{2}^{2} ≤ * **C*(**w**_{i})− *C*(**w**^{⋆}). |