Error Estimations for Total Variation Type Regularization

Abstract

This paper provides several error estimations for total variation (TV) type regularization, which arises in a series of areas, for instance, signal and imaging processing, machine learning, etc. In this paper, some basic properties of the minimizer for the TV regularization problem such as stability, consistency and convergence rate are fully investigated. Both a priori and a posteriori rules are considered in this paper. Furthermore, an improved convergence rate is given based on the sparsity assumption. The problem under the condition of non-sparsity, which is common in practice, is also discussed; the results of the corresponding convergence rate are also presented under certain mild conditions.

1. Introduction

Compressed sensing [1,2] has gained increasing attention in recent years; it plays an important role in signal processing [3,4], imaging science [5,6] and machine learning [7]. Compressed sensing focusses on signals with sparse presentation. Let ${\mathcal{H}}_1$ be a Hilbert space, and $\{e_i\in {\mathcal{H}}_1|i\in \mathbb{N}\}$ be the orthonormal basis of ${\mathcal{H}}_1$. For any $x\in {\mathcal{H}}_1$, let $x_i:=\langle x,e_i\rangle$. Given some operators K satisfy certain conditions, it is possible to recover a sparse $x^{†}\in {\mathbb{C}}^n$ signal with length n by Basis Pursuit (BP) [8], i.e.,

$${min||x||}_{1}s.t.y^{†}=Kx,$$

from the samples $y^{†}=K{x}^{†}$, even K is ill-posed [2,9,10]. However, in most cases, noise is inevitable. The literatures has turned to studying the noised BP model

$${min||x||}_{1}s.t.{\parallel Kx-y^{†}\parallel }_2\le \delta ,$$

where $\delta$ is the allowed error. Actually, the unconstrained form of the noised BP model, i.e., sparse regularization which is the focus in [11,12,13,14,15,16] is more attractive. While the success of compressed sensing greatly inspired the development of sparse regularization, it is interesting to see that sparse regularization appeared much earlier than compressed sensing [11,12]. As an inverse problem, the error theory of sparse regularization is well studied in the literature [17,18,19].

In practical terms, a large crowd of signals is not sparse unless being transformed by some operators (maybe ill posed). Thus, many studies have been proposed to analyze the regularized optimization problem [20]. A typical example of them is signal with a sparse gradient which arises frequently from imaging processing (nature images are usually piece-wise constant, i.e., they have a sparse gradient). The Total Variation (TV) has been used extensively in the literature for decades in imaging sciences and a series of techniques have been dedicated to researching its choice of regularization parameter [21,22,23,24,25,26,27,28,29,30,31]; others [32,33] are developed based on this observation. Similar to [34], Total Variation can also smooth the signal of interest. Let ${\mathcal{H}}_2$ be another Hilbert space. For any $x\in {\mathcal{H}}_1$, define that $T:{\mathcal{H}}_1\mapsto {\mathcal{H}}_1$ satisfies

$${(Tx)}_i:=x_i-x_{i+1}.$$

Under the above definition, T is an ill-posed linear operator. Given a linear map $K:{\mathcal{H}}_1\mapsto {\mathcal{H}}_2$ and $y^{\delta }\in {\mathcal{H}}_2$, the total variation regularization problem can be represented as

$${\mathrm{\Psi }}_{\alpha }(x)=\frac{1}{2}\parallel Kx-y^{\delta }{\parallel }_2^2+\alpha \sum _i|{(Tx)}_i|,$$

where $\alpha >0$ is the regularization parameter. The regularization term ${\sum }_i|{(Tx)}_i|$ is the right total variation (TV) of x. The TV type regularization has a similar form to the sparse regularization. However, the perfect reconstruction result established in sparse regularization can not be applied to theTV type directly, especially when T is ill-posed (T has a nontrivial null space).

So in this paper, firstly, we discuss the stability and consistency of the minimizers of ${\mathrm{\Psi }}_{\alpha }$. Besides basic properties, we are also interested in the convergence rate to solve the TV problem. Then, under the source conditions [19,35,36], convergence rates get obtained for both a priori and a posteriori parameter choice rules. However, the linear convergence rate requires K to be injective, which is strict usually. In the latter part, the linear convergence rate can also be derived under the sparsity assumption on $T{x}^{†}$ and some suitable conditions for K. This requirement of deduction does not depend on the injectivity of K. Meanwhile, this paper also considers the case when the sparsity assumption on $T{x}^{†}$ fails. Last, based on some recent works [37,38,39], which also assume the $T{x}^{†}$ is not sparse, a convergence rate is also given in this case.

The rest of this paper is organized as follows. Section 2 provides a brief summary of the notations. Section 3 presents some basic properties and gives the convergence rate of the minimizer. Section 4 proves the improved convergence rate. Finally, Section 5 concludes the whole paper.

2. Notation

The notations described in this section are adopted throughout this paper. Let ${\mathcal{H}}_1$, ${\mathcal{H}}_2$ be two Hilbert spaces and $\{e_i\in {\mathcal{H}}_1|i\in \mathbb{N}\}$, $\{{\xi }_i\in {\mathcal{H}}_2|i\in \mathbb{N}\}$ be the orthonormal basis of ${\mathcal{H}}_1$ and ${\mathcal{H}}_2$, respectively. For any $x\in {\mathcal{H}}_1$ and $y\in {\mathcal{H}}_2$, $x_i:=\langle x,e_i\rangle$ and $y_i:=\langle y,{\xi }_i\rangle$. The ${\ell }_1$ and ${\ell }_2$ norms of x and y are denoted by ${\parallel x\parallel }_{{\ell }^1}:={\sum }_i|x_i|$, ${\parallel x\parallel }_{{\ell }^2}:={({\sum }_i{|x_i|}^2)}^{\frac{1}{2}}$ and ${\parallel y\parallel }_1:={\sum }_i|y_i|$, ${\parallel y\parallel }_2:={({\sum }_i{|y_i|}^2)}^{\frac{1}{2}}$, respectively. In this paper, if not specified, for any $x\in {\mathcal{H}}_1$ and $y\in {\mathcal{H}}_2$, we assume that $x,y\in L^2$, i.e., ${\parallel x\parallel }_{{\ell }^2}<+\infty$ and ${\parallel y\parallel }_2<+\infty$. $x^n\rightharpoonup x$ means that $x^n$ converges weakly to x, while $x^n\to x$ means $x^n$ converges strongly to x. The operator norm of the linear operator $K:{\mathcal{H}}_1\mapsto {\mathcal{H}}_2$ is defined as

$$\parallel K\parallel :=\underset{{\parallel x\parallel }_{{\ell }^2}=1}{max}{\parallel Kx\parallel }_2.$$

Through the paper, $x^{†}$ means the signal of interest; $y^{†}:=K{x}^{†}$ are the measurements. $y^{\delta }$ denotes an element in ${\mathcal{H}}_2$ satisfying $\parallel y^{†}-y^{\delta }{\parallel }_2\le \delta$. Under these notations, the TV regularization can be expressed as

$${\mathrm{\Psi }}_{\alpha }(x)=\frac{1}{2}\parallel Kx-y^{\delta }{\parallel }_2^2+\alpha {\parallel Tx\parallel }_{{\ell }^1}.$$

Denote that $x_{\alpha }^{\delta }$ is one of the minimizers of ${\mathrm{\Psi }}_{\alpha }$.

Remark 1.

Considering the set $L={\left\{x^n\right\}}_{n=1,2,\dots }\subseteq {\mathcal{H}}_1$, where

$$\begin{array}{c}\hfill x_i^n:=\left\{\begin{array}{cc}1/\sqrt{n}\hfill & ifi\le n,\hfill \\ 0\hfill & ifi>n.\hfill \end{array}.\right.\end{array}$$

Obviously, for any n, $x^n\in L^2$ and $T(x^n)=1/\sqrt{n}$. As $n\to +\infty$, $\parallel x^n{\parallel }_{{\ell }^2}=1$ and $T(x^n)\to 0$. That means T is ill posed.

Remark 2.

Let $D=T-I_d$, where $I_d$ is the identical operator over ${\mathcal{H}}_1$. Then, ${(Dx)}_i=-x_{i+1}$ for any $i\in \mathbb{N}$. It is easy to verify that D is continuous. Then, T is continuous over ${\mathcal{H}}_1$ and

$$\parallel T-I_d\parallel =\parallel D\parallel \le 1.$$

(1)

In practice, The ill condition of T brings trouble to the analysis. To overcome this problem, we consider a condition which plays an important role in the deduction.

Condition 1.

There exist two constants$c,m>0$such that

$${c\parallel Kx\parallel }_2+{m\parallel Tx\parallel }_{{\ell }^2}\ge {\parallel x\parallel }_{{\ell }^2}$$

for any$x\in {\mathcal{H}}_1$.

We present a finite-dimensional understanding of this condition. Let $dim({\mathcal{H}}_1)=M$ and $dim({\mathcal{H}}_2)=N$. Then, $K\in {\mathcal{R}}^{M\times N}$ satisfies $null(K)\ne \mathbf{0}$ and $T\in {\mathcal{R}}^{(N-1)\times N}$. In the finite dimension case, T has the form

$${\left(\begin{array}{ccccc}1& -1& & & \\ & 1& -1& & \\ & & \ddots & \ddots & \\ & & & 1& -1\end{array}\right)}_{(N-1)\times N}.$$

The definition of T gives that $null(T)=span(\overrightarrow{\mathbf{1}})$. If $K\overrightarrow{\mathbf{1}}\ne \mathbf{0}$. Then, $null(K)\bigcap null(T)$$=\mathbf{0}$, we have that $null\left(\begin{array}{c}\widehat{c}K\\ \widehat{m}T\end{array}\right)=\mathbf{0}$, where $\widehat{c},\widehat{m}>0$. Hence, for any $x\in {\mathcal{R}}^n$ and some $\iota >0$, $\iota \parallel \left(\begin{array}{c}\widehat{c}K\\ \widehat{m}T\end{array}\right){x\parallel }_2\ge {\parallel x\parallel }_2$. Note that $\parallel \left(\begin{array}{c}\widehat{c}K\\ \widehat{m}T\end{array}\right){x\parallel }_2\le \widehat{c}{\parallel Kx\parallel }_2+\widehat{m}{\parallel Tx\parallel }_2$; we then have $\iota \widehat{c}{\parallel Kx\parallel }_2+\iota \widehat{m}{\parallel Tx\parallel }_2\ge {\parallel x\parallel }_2$.

3. Basic Error Estimations

The properties of TV type regularization are investigated in this section. First, a lemma is introduced which is used in this section frequently.

Lemma 1.

Let $y^{\delta }$ be bounded, α be fixed and ${\left\{x^n\right\}}_{n=1,2,\dots }$ be a sequence. Assume that Condition 1 holds and ${\left\{{\mathrm{\Psi }}_{\alpha }(x^n)\right\}}_{n=1,2,\dots }$ is bounded. Then, ${\left\{x^n\right\}}_{n=1,2,\dots }$ is also bounded.

Proof. 

It is trivial to prove $\{\parallel K{x}^n-y^{\delta }{{\parallel }_2\}}_{n=1,2,\dots }$ and $\{\parallel T{x}^n{{\parallel }_{{\ell }^1}\}}_{n=1,2,\dots }$ are bounded. Note that

$$\parallel T{x}^n{\parallel }_{{\ell }^2}\le \parallel T{x}^n{\parallel }_{{\ell }^1}\mathrm{and}\parallel K{x}^n{\parallel }_2\le \parallel K{x}^n-y^{\delta }{\parallel }_2+{\parallel y^{\delta }\parallel }_2,$$

which implies $\{\parallel K{x}^n{{\parallel }_2\}}_{n=1,2,\dots }$ and $\{\parallel T{x}^n{{\parallel }_{{\ell }^2}\}}_{n=1,2,\dots }$ are bounded. From Condition 1, we derive that

$$\parallel x^n{\parallel }_{{\ell }^2}\le c\parallel K{x}^n{\parallel }_2+m{\parallel T{x}^n\parallel }_{{\ell }^2}^{.}$$

implies the boundedness of ${\left\{x^n\right\}}_{n=1,2,\dots }$. □

3.1. Stability

In this subsection, we investigate the performance of $x_{\widehat{\alpha }}^{\delta }$ as $\widehat{\alpha }\to \alpha$, when $y^{\delta }$ is fixed. A lemma is introduced which arises in convex optimization.

Lemma 2

([40,41]). Let ${\chi }^{*}$ be the solution set of the convex minimization problem

$$\underset{x}{min}{\mathrm{\Psi }}_{\alpha }(x).$$

Then, $Kx$ and ${\parallel Tx\parallel }_1$ is constant over ${\chi }^{*}$.

Theorem 1.

Assume that $K,T$ satisfies Condition 1. For any fixed $\alpha >0$ and $y^{\delta }\in {\mathcal{H}}_2$, we have

$$\underset{{\alpha }_n\to \alpha }{lim}K{x}_{{\alpha }_n}^{\delta }=K{x}_{\alpha }^{\delta }.$$

(2)

Proof. 

The minimizing property of $x_{{\alpha }_n}^{\delta }$ gives that $\frac{1}{2}\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}_{{\alpha }_n}^{\delta }\parallel }_1\le {\mathrm{\Psi }}_{{\alpha }_n}(0)$. Then, Lemma 1 indicates that there exists a subsequence of $\left\{x_{{\alpha }_n}^{\delta }\right\}$ converging weakly to some $x^{*}\in {\ell }^2$. For simplicity, we also denote this subsequence as $\left\{x_{{\alpha }_n}^{\delta }\right\}$. By the weak lower continuity of the norms, we have

$$\parallel K{x}^{*}-y^{\delta }{\parallel }_2\le \underset{n}{lim\; inf}\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2\mathrm{and}\parallel T{x}^{*}{\parallel }_{{\ell }^1}\le \underset{n}{lim\; inf}{\parallel T{x}_{{\alpha }_n}^{\delta }\parallel }_{{\ell }^1}.$$

(3)

Therefore, we have that

$$\begin{array}{ccc}\hfill {\mathrm{\Psi }}_{\alpha }(x^{*})& =& \frac{1}{2}\parallel K{x}^{*}-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}^{*}\parallel }_1\hfill \\ & \le & \underset{n}{lim\; inf}\{\frac{1}{2}\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2^2+{\alpha }_n\parallel T{x}_{{\alpha }_n}^{\delta }{\parallel }_{{\ell }^1}\}\hfill \\ & =& \underset{n}{lim\; inf}{\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta }).\hfill \end{array}$$

On the other hand, by the minimizing property of $x_{{\alpha }_n}^{\delta }$,

$$\underset{n}{lim\; sup}{\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta })\le \underset{n}{lim\; sup}{\mathrm{\Psi }}_{{\alpha }_n}(x_{\alpha }^{\delta })=\underset{n}{lim}{\mathrm{\Psi }}_{{\alpha }_n}(x_{\alpha }^{\delta })={\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta }).$$

Obviously, it holds that

$$\underset{n}{lim\; sup}{\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta })\le {\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })\le {\mathrm{\Psi }}_{\alpha }(x^{*})\le \underset{n}{lim\; inf}{\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta }).$$

That means $x^{*}$ minimizes ${\mathrm{\Psi }}_{\alpha }(x)$. From Lemma 2, $K{x}^{*}=K{x}_{\alpha }^{\delta }$ and $\parallel T{x}^{*}{\parallel }_{{\ell }^1}={\parallel T{x}_{\alpha }^{\delta }\parallel }_{{\ell }^1}$. Consequently, we have $K{x}_{{\alpha }_n}^{\delta }\rightharpoonup K{x}_{\alpha }^{\delta }$, ${\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta })\to {\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })$ and $\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le {lim\; inf}_n{\parallel T{x}_{{\alpha }_n}^{\delta }\parallel }_{{\ell }^1}$. In the following, we present the proof by the mean of contradiction. Assume that $t:={lim\; sup}_n\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2>{\parallel K{x}_{\alpha }^{\delta }-y^{\delta }\parallel }_2$. We can obtain that

$$\begin{array}{ccc}\hfill \alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}& \le & \underset{n}{lim\; inf}\{\alpha \parallel T{x}_{{\alpha }_n}^{\delta }{\parallel }_{{\ell }^1}\}\hfill \\ & =& \underset{n}{lim\; inf}\{{\mathrm{\Psi }}_{{\alpha }_n}(x_{{\alpha }_n}^{\delta })-\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2^2\}\hfill \\ & =& {\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })-\underset{n}{lim\; sup}{\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }\parallel }_2^2\hfill \\ & =& \alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}+(\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2-t)\hfill \\ & <& \alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}.\hfill \end{array}$$

(4)

This is a contradiction. Then, we have

$$\underset{n}{lim\; sup}\parallel K{x}_{{\alpha }_n}^{\delta }-y^{\delta }{\parallel }_2\le {\parallel K{x}_{\alpha }^{\delta }-y^{\delta }\parallel }_2.$$

From relations (3), we can obtain that $K{x}_{{\alpha }_n}^{\delta }\to K{x}_{\alpha }^{\delta }$. □

If K is injective, we can further have that ${lim}_{{\alpha }_n\to \alpha }{x}_{{\alpha }_n}^{\delta }=x_{\alpha }^{\delta }$. The theorem above indicates that ${\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })$ and $\parallel T{x}_{\alpha }^{\delta }{\parallel }_1$ are continuous at $\alpha$. In fact, we can obtain a stronger result; the value function is differentiable at $\alpha$.

Theorem 2.

Let $F(\alpha ):={\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })$; then, $F(\alpha )$ is differentiable with respect to α, and $F^{\prime }(\alpha )={\parallel T{x}_{\alpha }^{\delta }\parallel }_1$.

Proof. 

For $\alpha >\widehat{\alpha }$, we have

$$\begin{array}{ccc}\hfill F(\alpha )-F(\widehat{\alpha })& =& \frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}-\frac{1}{2}{\parallel K{x}_{\widehat{\alpha }}^{\delta }-y^{\delta }\parallel }_2^2\hfill \\ & -& \alpha \parallel T{x}_{\widehat{\alpha }}^{\delta }{\parallel }_{{\ell }^1}+(\alpha -\widehat{\alpha }){\parallel T{x}_{\widehat{\alpha }}^{\delta }\parallel }_{{\ell }^1}.\hfill \end{array}$$

Due to that $x_{\alpha }^{\delta }$ minimizing ${\mathrm{\Psi }}_{\alpha }$, we have

$$\frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}-\frac{1}{2}\parallel K{x}_{\widehat{\alpha }}^{\delta }-y^{\delta }{\parallel }_2^2-\alpha {\parallel T{x}_{\widehat{\alpha }}^{\delta }\parallel }_{{\ell }^1}\le 0.$$

It follows that $F(\alpha )-F(\widehat{\alpha })\le (\alpha -\widehat{\alpha }){\parallel T{x}_{\widehat{\alpha }}^{\delta }\parallel }_{{\ell }^1}$. On the other hand, $F(\alpha )-F(\widehat{\alpha })$ can be written as

$$\begin{array}{ccc}\hfill F(\alpha )-F(\widehat{\alpha })& =& \frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\widehat{\alpha }\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}-\frac{1}{2}{\parallel K{x}_{\widehat{\alpha }}^{\delta }-y^{\delta }\parallel }_2^2\hfill \\ & -& \widehat{\alpha }\parallel T{x}_{\widehat{\alpha }}^{\delta }{\parallel }_{{\ell }^1}+(\alpha -\widehat{\alpha }){\parallel T{x}_{\alpha }^{\delta }\parallel }_{{\ell }^1}.\hfill \end{array}$$

Similarly, we have $F(\alpha )-F(\widehat{\alpha })\ge (\alpha -\widehat{\alpha }){\parallel T{x}_{\alpha }^{\delta }\parallel }_{{\ell }^1}$. Combining the two inequalities above, we have

$$\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le \frac{F(\alpha )-F(\widehat{\alpha })}{\alpha -\widehat{\alpha }}\le {\parallel T{x}_{\widehat{\alpha }}^{\delta }\parallel }_{{\ell }^1}.$$

When $\alpha <\widehat{\alpha }$, similar results can be also obtained. The continuity of $\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}$ at $\alpha$ gives that $\frac{dF(\alpha )}{d\alpha }={\parallel T{x}_{\alpha }^{\delta }\parallel }_{{\ell }^1}$. □

3.2. Consistency

The performance of $x_{\alpha }^{\delta }$ is investigated under a prior parameter choice as $\delta \to 0$. In the analysis, we assume that the following conditions hold.

Condition 2.

For any$x\in {\mathcal{H}}_1$obeying$Kx=y^{†}$, $x^{†}$satisfies that

$$\parallel T{x}^{†}{\parallel }_{{\ell }^1}\le {\parallel Tx\parallel }_{{\ell }^1}.$$

The equality holds if and only if$x=x^{†}$.

Lemma 3.

Let ${\left\{x^n\right\}}_n\rightharpoonup x^{*}$, $\parallel K{x}^n-y^{†}{\parallel }_2^2\to {\parallel K{x}^{*}-y^{†}\parallel }_2^2$ and $\parallel T{x}^n{\parallel }_{{\ell }^1}\to {\parallel T{x}^{*}\parallel }_{{\ell }^1}$. Then, we have $\parallel T(x^n-x^{*}){\parallel }_{{\ell }^1}\to 0$ and $\parallel K(x^n-x^{*}){\parallel }_2\to 0$.

Proof. 

We can obtain that

$$\begin{array}{ccc}\hfill \underset{n}{lim\; sup}{\parallel T(x^n-x^{*})\parallel }_{{\ell }^1}& =& \underset{n}{lim\; sup}((\parallel T{x}^n{\parallel }_{{\ell }^1}+\parallel T{x}^{*}{\parallel }_{{\ell }^1})\hfill \\ & -& (\parallel T{x}^n{\parallel }_{{\ell }^1}+\parallel T{x}^{*}{\parallel }_{{\ell }^1})+\parallel T(x^n-x^{*}){\parallel }_{{\ell }^1}))\hfill \\ & =& 2\parallel T{x}^{*}{\parallel }_{{\ell }^1}-\underset{n}{lim\; inf}((\parallel T{x}^n{\parallel }_{{\ell }^1}+\parallel T{x}^{*}{\parallel }_{{\ell }^1})\hfill \\ & -& \parallel T(x^n-x^{*}){\parallel }_{{\ell }^1}).\hfill \end{array}$$

The triangle inequality gives that $(\parallel T{x}^n{\parallel }_{{\ell }^1}+\parallel T{x}^{*}{\parallel }_{{\ell }^1})-\parallel T(x^n-x^{*}){\parallel }_{{\ell }^1}\ge 0$. The Fatou’s lemma gives that

$$\begin{array}{ccc}\hfill \underset{n}{lim\; inf}((\parallel T{x}^n{\parallel }_{{\ell }^1}& +& \parallel T{x}^{*}{\parallel }_{{\ell }^1})-\parallel T(x^n-x^{*}){\parallel }_{{\ell }^1})\hfill \\ & =& \underset{n}{lim\; inf}(\sum _i|{(T{x}^n)}_i|+|{(T{x}^{*})}_i|-|{(T(x^n-x^{*}))}_i|)\hfill \\ & \le & \sum _i\underset{n}{lim\; inf}(|{(T{x}^n)}_i|+|{(T{x}^{*})}_i|-|{(T(x^n-x^{*}))}_i|).\hfill \end{array}$$

Note that $x^n-x^{*}\rightharpoonup \mathbf{0}$; then, $T(x^n-x^{*})\rightharpoonup T\mathbf{0}=\mathbf{0}$. Hence, ${\left[T(x^n-x^{*})\right]}_i\to 0$. Similarly, we can obtain ${(T{x}^n)}_i\to {(T{x}^{*})}_i$. Therefore,

$$\sum _i\underset{n}{lim\; inf}(|{(T{x}^n)}_i|+|{(T{x}^{*})}_i|-|{(T(x^n-x^{*}))}_i|)=\sum _{i}2|{(T{x}^{*})}_i|=2\parallel T{x}^{*}{\parallel }_{{\ell }^1}.$$

Thus, we have

$$\underset{n}{lim\; sup}{\parallel T(x^n-x^{*})\parallel }_{{\ell }^1}=0.$$

By the same method, we also can obtain that $\parallel K(x^n-x^{*}){\parallel }_2\to 0$. □

Theorem 3.

Assume that $K,T$ satisfies Condition 1 and Lemma 1. Let the parameters satisfy that

$$\alpha (\delta ),\frac{{\delta }^2}{\alpha (\delta )}\to 0as\delta \to 0.$$

Then the sequence ${\left\{x_{\alpha }^{\delta }\right\}}_{\delta }\to x^{†}$.

Proof. 

By the definition of $x_{\alpha }^{\delta }$, we have

$$\begin{array}{ccc}\hfill \frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}_{\alpha }^{\delta }\parallel }_{{\ell }^1}& \le & \frac{1}{2}\parallel K{x}^{†}-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}^{†}\parallel }_{{\ell }^1}\hfill \\ & \le & \frac{1}{2}{\delta }^2+\alpha {\parallel T{x}^{†}\parallel }_{{\ell }^1}.\hfill \end{array}$$

From the parameters’ choice rule of $\alpha$ and $\delta$, we can see that $\left\{{\mathrm{\Psi }}_{\alpha }(x_{\alpha }^{\delta })\right\}$ are bounded. Then, from Lemma 1, there exists a subsequence also denoted by ${\left\{x_{\alpha }^{\delta }\right\}}_{\delta }$ and some point $x^{*}$ such that $x_{\alpha }^{\delta }\rightharpoonup x^{*}$. We can have that

$$\begin{array}{ccc}\hfill \parallel K{x}^{*}-y^{†}{\parallel }_2^2& \le & \underset{\delta }{lim\; inf}{\parallel K{x}_{\alpha }^{\delta }-y^{†}\parallel }_2^2\hfill \\ & \le & 2\underset{\delta }{lim\; inf}(\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\parallel y^{\delta }-y^{†}{\parallel }_2^2)\hfill \\ & \le & \underset{\delta }{lim\; inf}({\delta }^2+2\alpha (\delta )\parallel T{x}^{†}{\parallel }_{{\ell }^1}+{\delta }^2)=0.\hfill \end{array}$$

This means $K{x}^{*}=y^{†}$. It is easy to see that ${lim}_{\delta }{\parallel K{x}_{\alpha }^{\delta }-y^{†}\parallel }_2^2=0$. On the other hand, we can obtain that

$$\begin{array}{c}\hfill \parallel T{x}^{*}{\parallel }_{{\ell }^1}\le \underset{\delta }{lim\; inf}\{\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}+\frac{{\delta }^2}{2\alpha (\delta )}\}=\parallel T{x}^{†}{\parallel }_{{\ell }^1}.\end{array}$$

Condition 2 gives that $x^{*}=x^{†}$. From the inequality above, we see that ${lim}_{\delta }\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}={\parallel T{x}^{†}\parallel }_{{\ell }^1}.$ By Lemma 3, we have $\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^1}\to 0$ and $\parallel K(x_{\alpha }^{\delta }-x^{*}){\parallel }_2\to 0$. Consequently, from Condition 1, it holds that

$$\begin{array}{ccc}\hfill \underset{\delta }{lim}{\parallel x_{\alpha }^{\delta }-x^{*}\parallel }_{{\ell }^2}& \le & \underset{\delta }{lim}m\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^2}+c{\parallel K(x_{\alpha }^{\delta }-x^{*})\parallel }_2\hfill \\ & \le & \underset{\delta }{lim}m\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^1}+c{\parallel K(x_{\alpha }^{\delta }-x^{*})\parallel }_2=0.\hfill \end{array}$$

 □

3.3. Convergence Rate

This subsection concerns the convergence rate under different parameter choice rules (a priori and a posteriori). First, we discuss the a priori one. Like the classical Tikhonov regularization method [19,35,36], we introduce a source condition.

Condition 3.

Let$x^{†}$satisfy the source condition

$$\exists w:K^{*}w\in T^{*}\partial {\parallel T{x}^{†}\parallel }_{{\ell }^1}.$$

Theorem 4.

If $x^{†}$ satisfies the source condition, it holds that

$$\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2\le 2\alpha {\parallel w\parallel }_2+\delta .$$

If K is injective, there exists $\gamma >0$ such that

$$\parallel x_{\alpha }^{\delta }-x^{†}{\parallel }_{{\ell }^2}\le 2\gamma \alpha {\parallel w\parallel }_2+2\gamma \delta .$$

Proof. 

The definition of $x_{\alpha }^{\delta }$ gives that

$$\frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le \frac{1}{2}\parallel K{x}^{†}-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}^{†}\parallel }_{{\ell }^1}.$$

Using the notation $C(x)={\parallel Tx\parallel }_{{\ell }^1}$, we obtain that

$$\frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha C(x_{\alpha }^{\delta })\le \frac{1}{2}{\parallel K{x}^{†}-y^{\delta }\parallel }_2^2+\alpha C(x^{†}).$$

For any $v\in \partial C(x^{†})$, the convexity of C indicates $C(x_{\alpha }^{\delta })\ge C(x^{†})+\langle v,x_{\alpha }^{\delta }-x^{†}\rangle$. Then, we have that

$$\begin{array}{ccc}\hfill \frac{1}{2}{\parallel K{x}_{\alpha }^{\delta }-y^{\delta }\parallel }_2^2+\alpha C(x^{†})& +& \alpha \langle v,x_{\alpha }^{\delta }-x^{†}\rangle \hfill \\ & \le & \frac{1}{2}{\parallel K{x}_{\alpha }^{\delta }-y^{\delta }\parallel }_2^2+\alpha C(x_{\alpha }^{\delta })\hfill \\ & \le & \frac{1}{2}{\parallel K{x}^{†}-y^{\delta }\parallel }_2^2+\alpha C(x^{†}).\hfill \end{array}$$

Choose $v=K^{*}w$ in the source condition; after simplification, we derive that

$$\frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha \langle w,K{x}_{\alpha }^{\delta }-y^{\delta }\rangle \le \frac{1}{2}{\parallel K{x}^{†}-y^{\delta }\parallel }_2^2+\alpha \langle w,K{x}^{†}-y^{\delta }\rangle .$$

By adding both sides with $\frac{{\alpha }^2{\parallel w\parallel }_2^2}{2}$, we obtain that

$$\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{+\alpha w\parallel }_2\le {\parallel K{x}^{†}-y^{\delta }+\alpha w\parallel }_2.$$

This means

$$\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2\le {2\alpha \parallel w\parallel }_2+\parallel K{x}^{†}-y^{\delta }{\parallel }_2\le 2\alpha {\parallel w\parallel }_2+\delta .$$

If K is injective, there exists $\gamma >0$ such that ${\parallel x\parallel }_{{\ell }^2}\le \gamma {\parallel Kx\parallel }_{{\ell }^2}$. Then, we derive that

$$\begin{array}{ccc}\hfill \parallel x_{\alpha }^{\delta }-x^{†}{\parallel }_2& \le & \gamma \parallel K{x}_{\alpha }^{\delta }-y^{†}{\parallel }_2\hfill \\ & \le & \gamma (\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2+\parallel y^{\delta }-y^{†}\parallel )\hfill \\ & \le & \gamma (2\alpha \parallel w{\parallel }_2+2\delta ).\hfill \end{array}$$

 □

Remark 3.

In fact, the first result in Theorem 4 has been proved by [42] for general convex regularization. The proof here is for the completeness.

The following part investigates the a posteriori parameter choice rule. The analysis is motivated by the work in [43,44]. For simplicity of presentation, the parameter $\alpha$ is chosen as

$$\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2=\delta .$$

(5)

Theorem 5.

Assume that α is chosen as rule (5), and $x^{†}$ satisfies Condition 2. It then holds that

$$\underset{\delta \to 0}{lim}{x}_{\alpha }^{\delta }=x^{†}.$$

If K is injective, there exists $\theta >0$ such that

$$\parallel x_{\alpha }^{\delta }-x^{*}{\parallel }_{{\ell }^2}\le 2\theta \delta .$$

Proof. 

It is trivial to prove that

$$\frac{1}{2}\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2^2+\alpha \parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le \frac{1}{2}\parallel K{x}^{†}-y^{\delta }{\parallel }_2^2+\alpha {\parallel T{x}^{†}\parallel }_{{\ell }^1}.$$

Lemma 2 indicates that ${\left\{x_{\alpha }^{\delta }\right\}}_{\delta }$ is bounded. Note that $\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2=\delta$ and $\parallel K{x}^{†}-y^{\delta }{\parallel }_2\le \delta$. It then follows that

$$\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le {\parallel T{x}^{†}\parallel }_{{\ell }^1}.$$

(6)

Then, the sequence has a sub-sequence also denoted by ${\left\{x_{\alpha }^{\delta }\right\}}_{\delta }$ converging weakly to some $x^{*}$. We can easily see that

$$\begin{array}{ccc}\hfill \parallel K{x}^{*}-y^{†}{\parallel }_2& \le & \underset{\delta \to 0}{lim\; inf}{\parallel K{x}_{\alpha }^{\delta }-y^{†}\parallel }_2\hfill \\ & \le & \underset{\delta \to 0}{lim\; inf}(\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2+\parallel y^{\delta }-y^{†}{\parallel }_2)\hfill \\ & \le & \underset{\delta \to 0}{lim\; inf}2\delta =0.\hfill \end{array}$$

That is actually to say that $K{x}^{*}=y^{†}$. Moreover, it is easy to see that ${lim}_{\delta }{\parallel K{x}_{\alpha }^{\delta }-y^{†}\parallel }_2^2=0$. Using relation (6), we have that

$$\parallel T{x}^{*}{\parallel }_{{\ell }^1}\le \underset{\delta \to 0}{lim\; inf}\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\le {\parallel T{x}^{†}\parallel }_{{\ell }^1}.$$

Condition 2 gives that $x^{*}=x^{†}$; hence, the whole sequence converges weakly to $x^{†}$ and

$$\parallel T{x}^{†}{\parallel }_{{\ell }^1}\le \underset{\delta \to 0}{lim\; inf}(\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1})\le \underset{\delta \to 0}{lim\; sup}(\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1})\le \parallel T{x}^{†}{\parallel }_{{\ell }^1}.$$

Thus, we have $\parallel T{x}_{\alpha }^{\delta }{\parallel }_{{\ell }^1}\to {\parallel T{x}^{†}\parallel }_{{\ell }^1}$. From Lemma 3, we have $\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^1}\to 0$ and $\parallel K(x_{\alpha }^{\delta }-x^{*}){\parallel }_2\to 0$ which leads to

$$\begin{array}{ccc}\hfill \parallel x_{\alpha }^{\delta }-x^{*}{\parallel }_{{\ell }^2}& \le & m\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^2}+c{\parallel K(x_{\alpha }^{\delta }-x^{*})\parallel }_2\hfill \\ & \le & m\parallel T(x_{\alpha }^{\delta }-x^{*}){\parallel }_{{\ell }^1}+c{\parallel K(x_{\alpha }^{\delta }-x^{*})\parallel }_2\to 0.\hfill \end{array}$$

(7)

If K is injective, there exists $\theta >0$ such that ${\parallel x\parallel }_{{\ell }^2}\le \theta {\parallel Kx\parallel }_{{\ell }^2}$. Then, we derive that

$$\begin{array}{ccc}\hfill \parallel x_{\alpha }^{\delta }-x^{†}{\parallel }_2& \le & \theta \parallel K{x}_{\alpha }^{\delta }-y^{†}{\parallel }_2\hfill \\ & \le & \theta (\parallel K{x}_{\alpha }^{\delta }-y^{\delta }{\parallel }_2+\parallel y^{\delta }-y^{†}\parallel )\le 2\theta \delta .\hfill \end{array}$$

 □

4. Improved Convergence Rate

In this section, we investigate the convergence rate when K may be not injective. The first part presents the analysis under the sparse assumption while the second one deals with the case when the sparsity assumption fails.

4.1. Performance under Sparsity Assumption

The analysis in this subsection assumes that $T{x}^{†}$ is sparse. To prove the convergence rate we need the finite injectivity property [45].

Condition 4.

The operatorKsatisfies the uniformly finite injectivity property, i.e., for any finite subset$S\subseteq \mathbb{N}$, ${K|}_S$is injective.

Remark 4.

In the finite dimension case, if $♯supp(S)$ is small, it is easy to find that the finite injectivity property is actually the restrict isometry property [2,46].

Let $z:=Tx$ and $z^{†}:=T{x}^{†}$. Denote S as the set $S:=\{i\in \mathbb{N}:|v_i|>\frac{1}{2}\}$, where $v\in \partial \parallel z^{†}{\parallel }_{{\ell }^1}$ satisfies the source condition. Let $m={sup}_{i\notin S}\{|v_i|\}$. Due to that $v\in {\ell }^2$, S is finite and it contains the support of $z^{†}$. Let P be the identical projection onto S and $P^{\perp }$ be the one onto $\mathbb{N}\backslash S$. From Condition 4, there exists some $d>0$ such that

$${d\parallel KPz\parallel }_2\ge {\parallel Pz\parallel }_{{\ell }^2}.$$

Lemma 4.

Assume that $x^{†}$ satisfies the source condition and Condition 1 holds. If $md\parallel K\parallel <1$, there exist $c_1>0$ and $c_2>0$ such that

$${\parallel Tx\parallel }_{{\ell }^1}-\parallel T{x}^{†}{\parallel }_{{\ell }^1}\ge c_1\parallel x-x^{†}{\parallel }_{{\ell }^2}-c_2{\parallel T(x-x^{†})\parallel }_2.$$

Proof. 

Assume the conditions in Lemma 4 are held. Then, we can obtain that

$$\begin{array}{ccc}\hfill \parallel z-z^{†}{\parallel }_{{\ell }^2}& \le & \parallel P(z-z^{†}){\parallel }_{{\ell }^2}+{\parallel P^{\perp }(z-z^{†})\parallel }_{{\ell }^2}\hfill \\ & \le & d\parallel KP(z-z^{†}){\parallel }_2+{\parallel P^{\perp }z\parallel }_{{\ell }^2}\hfill \\ & \le & d\parallel K(z-z^{†}){\parallel }_2+(1+d\parallel K\parallel )\parallel P^{\perp }{z\parallel }_{{\ell }^2}.\hfill \end{array}$$

Hence, we derive that

$$\begin{array}{ccc}\hfill \parallel K(z-z^{†}){\parallel }_2& =& \parallel KT(x-x^{†}){\parallel }_2\hfill \\ & \le & \parallel K(x-x^{†}){\parallel }_2+{\parallel K(T-I_d)(x-x^{†})\parallel }_2\hfill \\ & \le & \parallel K(x-x^{†}){\parallel }_2+\parallel K\parallel ·\parallel T-I_d\parallel ·\parallel x-x^{†}{\parallel }_{{\ell }^2}\hfill \\ & \le & \parallel K(x-x^{†}){\parallel }_2+\parallel K\parallel ·\parallel x-x^{†}{\parallel }_{{\ell }^2}.\hfill \end{array}$$

We now turn to estimating $\parallel P^{\perp }{z\parallel }_{{\ell }^2}$. Let $m={sup}_{i\notin S}\{|v_i|\}$. Obviously, $m\le \frac{1}{2}$. We then have that

$$\begin{array}{ccc}\hfill \parallel P^{\perp }{z\parallel }_{{\ell }^2}& \le & \sum _{i\notin S}|z_i|\le 2\sum _{i\notin S}(1-m)|z_i|\le 2\sum _{i\notin S}(|z_i|-v_i{z}_i)\hfill \\ & \le & 2\sum _{i\notin S}(|z_i|-|z_i^{†}|-v_i(z_i-z_i^{†}))\hfill \\ & \le & 2(\parallel z{\parallel }_{{\ell }^1}-\parallel z^{†}{\parallel }_{{\ell }^1}-\langle v,z-z^{†}\rangle )\hfill \\ & =& 2(\parallel Tx{\parallel }_{{\ell }^1}-\parallel T{x}^{†}{\parallel }_{{\ell }^1}-\langle v,z-z^{†}\rangle ).\hfill \end{array}$$

The source condition gives that

$$\begin{array}{ccc}\hfill -\langle v,z-z^{†}\rangle & =& -\langle v,Tx-T{x}^{†}\rangle =-\langle T^{*}v,x-x^{†}\rangle \hfill \\ & =& -\langle K^{*}w,x-x^{†}\rangle =-\langle w,Kx-K{x}^{†}\rangle \hfill \\ & \le & {\parallel w\parallel }_2·{\parallel Kx-K{x}^{†}\parallel }_2.\hfill \end{array}$$

Therefore, we have that

$$\begin{array}{ccc}\hfill \parallel z-z^{†}{\parallel }_{{\ell }^2}& \le & d\parallel K\parallel ·\parallel x-x^{†}{\parallel }_{{\ell }^2}{+2(1+d\parallel K\parallel )(\parallel Tx\parallel }_{{\ell }^1}-\parallel T{x}^{†}{\parallel }_{{\ell }^1})\hfill \\ & +& {(2\parallel w\parallel }_2+{2d\parallel K\parallel \parallel w\parallel }_2+d)\parallel K(x-x^{†}){\parallel }_2.\hfill \end{array}$$

From Condition 1, we have that

$$\begin{array}{ccc}\hfill \parallel x-x^{†}{\parallel }_{{\ell }^2}& =& c\parallel K(x-x^{†}){\parallel }_2+m{\parallel Tx-T{x}^{†}\parallel }_{{\ell }^2}\hfill \\ & \le & c\parallel K(x-x^{†}){\parallel }_2+m{\parallel z-z^{†}\parallel }_{{\ell }^2}\hfill \\ & \le & md\parallel K\parallel ·\parallel x-x^{†}{\parallel }_{{\ell }^2}{+2(m+md\parallel K\parallel )(\parallel Tx\parallel }_1-\parallel T{x}^{†}{\parallel }_1)\hfill \\ & +& {(2m\parallel w\parallel }_2+{2dm\parallel K\parallel \parallel w\parallel }_2+md+c)\parallel K(x-x^{†}){\parallel }_2.\hfill \end{array}$$

Note that $md\parallel K\parallel <1$; let $q=\frac{1}{1-md\parallel K\parallel }$; we have that

$$\begin{array}{ccc}\hfill \parallel x-x^{†}{\parallel }_{{\ell }^2}& \le & {2q(m+md\parallel K\parallel )(\parallel Tx\parallel }_1-\parallel T{x}^{†}{\parallel }_1)\hfill \\ & +& {q(2m\parallel w\parallel }_2+{2md\parallel K\parallel \parallel w\parallel }_2+md+c)\parallel K(x-x^{†}){\parallel }_2.\hfill \end{array}$$

 □

With the lemma above, we can obtain the following result. The proofs can be found in [44,47,48,49].

Theorem 6.

Let the regularization parameter be chosen a priori as $\alpha (\delta )=\mathcal{O}(\delta )$ or a posteriori as $\alpha (\delta )$ according to the strong discrepancy principle (5) Then we have the convergence rate

$$\parallel x_{\alpha }^{\delta }-x^{†}{\parallel }_{{\ell }^2}=\mathcal{O}(\delta ).$$

4.2. Performance if Sparsity Assumption Fails

In this subsection, we focus on the case where $T{x}^{†}$ is not sparse. As presented in the last section, lemma 4 is critical for the convergence rate analysis. In this part, a similar lemma will be proposed. Then, the convergence rate will be proved. The first lemma is motivated by [37].

Lemma 5.

For any $x\in {\mathcal{H}}_1$ and $n\in \mathbb{N}$, it holds that

$$\parallel T(x-x^{†}){\parallel }_{{\ell }^1}-{\parallel Tx\parallel }_{{\ell }^1}+\parallel T{x}^{†}{\parallel }_{{\ell }^1}\le 2(\sum _{k=n+1}^{\infty }|{(T{x}^{†})}_k|+\sum _{k=1}^n|{(Tx)}_k-{(T{x}^{†})}_k|).$$

Proof. 

Denote the projection $P_n(x)=(x_1,x_2,\dots ,x_n,0,\dots )$ for any $x\in {\mathcal{H}}_1$. Hence, we have

$${\parallel Tx\parallel }_{{\ell }^1}=\parallel P_n{Tx\parallel }_{{\ell }^1}+{\parallel (I_d-P_n)Tx\parallel }_{{\ell }^1}.$$

Algebra computation gives that

$$\begin{array}{ccc}\hfill \parallel T(x-x^{†}){\parallel }_{{\ell }^1}& -& {\parallel Tx\parallel }_{{\ell }^1}+\parallel T{x}^{†}{\parallel }_{{\ell }^1}=\parallel P_{n}T(x-x^{†}){\parallel }_{{\ell }^1}+{\parallel (I_d-P_n)T{x}^{†}\parallel }_{{\ell }^1}\hfill \\ & +& \parallel (I_d-P_n)(Tx-T{x}^{†}){\parallel }_{{\ell }^1}-{\parallel (I_d-P_n)Tx\parallel }_{{\ell }^1}\hfill \\ & +& \parallel P_{n}T{x}^{†}{\parallel }_{{\ell }^1}-{\parallel P_{n}Tx\parallel }_{{\ell }^1}.\hfill \end{array}$$

Note that

$$\parallel (I_d-P_n)(Tx-T{x}^{†}){\parallel }_{{\ell }^1}\le \parallel (I_d-P_n){Tx\parallel }_{{\ell }^1}+{\parallel (I_d-P_n)T{x}^{†}\parallel }_{{\ell }^1}$$

and

$$\parallel P_{n}T{x}^{†}{\parallel }_{{\ell }^1}\le \parallel P_{n}T(x-x^{†}){\parallel }_{{\ell }^1}+{\parallel P_{n}Tx\parallel }_{{\ell }^1}.$$

Combining the equations above, we obtain

$$\parallel T(x-x^{†}){\parallel }_1-{\parallel Tx\parallel }_{{\ell }^1}+\parallel T{x}^{†}{\parallel }_{{\ell }^1}\le 2\parallel P_{n}T(x-x^{†}){\parallel }_{{\ell }^1}+2{\parallel (I_d-P_n)T{x}^{†}\parallel }_{{\ell }^1}.$$

 □

Condition 5.

For all$k\in \mathbb{N}$there exists$f_k\in {\mathcal{H}}_2$such that$T^{*}{e}_k=K^{*}{f}_k$and${lim}_{k\to \infty }{\parallel f_k\parallel }_2\to +\infty$.

Lemma 6.

Let $\phi (t):=2{inf}_n\{{\sum }_{k=n+1}^{\infty }|{(T{x}^{†})}_k|+t{\sum }_{k=1}^n\parallel f_k\parallel \}$; $\phi (t)$ is concave index function. Assume that $x^{†}$ satisfies the source condition and Conditions 1 and 5 hold. If $c\parallel K\parallel <1$, it holds that

$$\parallel x-x^{†}{\parallel }_{{\ell }^2}\le c_1{\parallel Tx\parallel }_{{\ell }^1}-c_2\parallel T{x}^{†}{\parallel }_{{\ell }^1}+c_3\phi (\parallel K(x-x^{†}){\parallel }_2)$$

for some positive$c_1,c_2,c_3$.

Proof. 

$\phi$ is concave and upper semi-continuous since it is an infimum of affine functions. For any $t\ge 0$, $\phi$ is finite and continuous. Note that $\phi (0)=0$; the upper semi-continuity at $t=0$ gives the continuity of $\phi$ at $t=0$. We turn to the strict monotonicity of $\phi$. Condition 5 means the infimum of $\phi (t)$ is attained at some $n\in \mathbb{N}$. Considering $0<t_1<t_2<+\infty$, we have

$$\begin{array}{ccc}\hfill \phi (t_1)& =& 2(\sum _{k=n_1+1}^{\infty }|{(T{x}^{†})}_k|+t_1\sum _{k=1}^{n_1}\parallel f_k{\parallel }_2)\hfill \\ & \le & 2(\sum _{k=n_2+1}^{\infty }|{(T{x}^{†})}_k|+t_1\sum _{k=1}^{n_2}\parallel f_k{\parallel }_2)\hfill \\ & <& 2(\sum _{k=n_2+1}^{\infty }|{(T{x}^{†})}_k|+t_2\sum _{k=1}^{n_2}\parallel f_k{\parallel }_2)=\phi (t_2).\hfill \end{array}$$

From Condition 5, we have that

$$\begin{array}{ccc}\hfill \sum _{k=1}^n|{(Tx-T{x}^{†})}_k|& =& \sum _{k=1}^n|\langle Tx-T{x}^{†},e_k\rangle |\hfill \\ & =& \sum _{k=1}^n|\langle x-x^{†},T^{*}{e}_k\rangle |\hfill \\ & =& \sum _{k=1}^n|\langle x-x^{†},K^{*}{f}_k\rangle |\hfill \\ & \le & \parallel K(x-x^{†}){\parallel }_2\sum _{k=1}^n{\parallel f_k\parallel }_2.\hfill \end{array}$$

(8)

Therefore, we obtain that

$$\begin{array}{c}\hfill \parallel T(x-x^{†}){\parallel }_{{\ell }^2}\le {\parallel Tx\parallel }_{{\ell }^1}-\parallel T{x}^{†}{\parallel }_{{\ell }^1}+2\phi (\parallel K(x-x^{†}){\parallel }_2).\end{array}$$

From Condition 1, we have that

$$\begin{array}{ccc}\hfill \parallel x-x^{†}{\parallel }_{{\ell }^2}& \le & c\parallel K(x-x^{†}){\parallel }_{{\ell }^2}+m{\parallel T(x-x^{†})\parallel }_2\hfill \\ & \le & c\parallel K\parallel \parallel x-x^{†}{\parallel }_{{\ell }^2}+{m\parallel Tx\parallel }_{{\ell }^1}-m{\parallel T{x}^{†}\parallel }_{{\ell }^1}\hfill \\ & +& 2m\phi (\parallel K(x-x^{†}){\parallel }_2).\hfill \end{array}$$

Let $q=\frac{1}{1-c\parallel K\parallel }$, we obtain that

$$\parallel x-x^{†}{\parallel }_{{\ell }^2}\le {qm\parallel Tx\parallel }_{{\ell }^1}-qm\parallel T{x}^{†}{\parallel }_{{\ell }^1}+2qm\phi (\parallel K(x-x^{†}){\parallel }_2).$$

 □

Theorem 7.

Let the regularization parameter be chosen a priori as $\alpha (\delta )=\mathcal{O}(\frac{{\delta }^2}{\phi (\delta )})$ or a posteriori as $\alpha (\delta )$ according to the strong discrepancy principle (5). Then we have the convergence rate

$$\parallel x_{\alpha }^{\delta }-x^{†}{\parallel }_{{\ell }^2}=\mathcal{O}(\phi (\delta )).$$

5. Conclusions

In this paper, we study some problems in total variation type regularization. While owning a familiar form as the sparse regularization, the TV type is hard to investigate for the ill condition of T. A group of regularization conditions has been given in this paper. Under these conditions, we study several theoretical properties such as stability, consistency and convergence rates of the minimizer of the TV type regularization. These analyses are deepened for the convergence rate under the assumption of sparsity. In the non-sparse case, we also present a conservative result based on some recent works. Now, the regularizers learned from the data are all the rage in research. So, in future work, we will make the error estimations for this type of regularization problem.