Exact Reconstruction using Beurling Minimal Extrapolation

Introduction

In the last decade much emphasis has been put on the exact reconstruction of sparse finite dimensional vectors using the basis pursuit algorithm. The pioneering paper of Chen, Donoho and Saunders [CDS01] has brought this method to the statistics community. Note that the seminal ideas on the subject appeared in earlier works of Donoho and Stark [DS89]. Therein, mainly the discrete Fourier transform is considered. Similarly, P. Doukhan, E. Gassiat and one author of this present paper [DG96, GG96] considered the exact reconstruction of a nonnegative measure. More precisely, they derived results when one only knows the values of a finite number of linear functionals at the target measure. Moreover, they study stability with respect to a metric for weak convergence which is not the case here.

In this paper, we are concerned with the measure framework. We show that the exact reconstruction of a signed measure is still possible when one only knows a finite number of non-adaptive linear measurements. Surprisingly our method, called generalized minimal extrapolation, appears to uncover exact reconstruction results related to basis pursuit.

Let us explain more precisely what is done here. Consider a signed discrete measure $\sigma$ on a set $I$. Unless otherwise specified, assume that $I:=$. Note that all our results easily extend to any real bounded set. Consider the Jordan decomposition,

and denote by $\mathcal{S}^{+}$ (resp. $\mathcal{S}^{-}$) the support of $\sigma^{+}$ (resp. $\sigma^{-}$). Let us define the Jordan support of the measure $\sigma$ as the pair $\mathcal{J}:=(\mathcal{S}^{+},\mathcal{S}^{-})$. Assume further that $\mathcal{S}:=\mathcal{S}^{+}\cup\mathcal{S}^{-}$ is finite and has cardinality $s$. Moreover suppose that $\mathcal{J}$ belongs to a family $\varUpsilon$ of pairs of subsets of $I$ (see Definition 1 for more details). We call $\varUpsilon$ a Jordan support family. The measure $\sigma$ can be written as

where $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}$, $\sigma_{1},\dotsc,\sigma_{s}$ are nonzero real numbers, and $\delta_{x}$ denotes the Dirac measure at point $x$.

Let $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ be any family of continuous functions on $\overline{I}$, where the set $\overline{I}$ denotes the closure of $I$ (this statement is meant to be general and encompasses the case where $I$ is not closed). Let $\mu$ be a signed measure on $I$. The $k$-th generalized moment of $\mu$ is defined by

We are concerned with the reconstruction of the target measure $\sigma$ from the observation of $\mathcal{K}_{n}:=(c_{0}(\sigma),\dotsc,c_{n}(\sigma))$, i.e. its first $(n+1)$ generalized moments. We assume that both the support $\mathcal{S}$ and the weights $\sigma_{i}$ of the target measure $\sigma$ are unknown. We investigate if it is possible to recover $\sigma$ uniquely from the observation of $\mathcal{K}_{n}$. More precisely, does an algorithm fitting $\mathcal{K}_{n}(\sigma)$ among all the signed measures of $I$ recover the measure $\sigma$?

Note that a finite number of assigned standard moments does not define a unique signed measure. In fact one can check that for each signed measure $\mu$ and for each integer $m\geq 1$ there exists a measure $\mu^{\prime}\neq\mu$ having the same first $m$ moments. It seems there is no hope of recovering discrete measures from a finite number of its generalized moments. Surprisingly, we show that every extrema Jordan type measure $\sigma$ (see Definition 1 and the examples that follow) is the unique solution of a total variation minimizing algorithm, generalized minimal extrapolation.

Basis pursuit

Generalized minimal extrapolation

Denote by $\mathcal{M}$ the set of finite signed measures on $I$ and by $\left\lVert\,.\,\right\lVert_{TV}$ the total variation norm. We recall that for all $\mu\in\mathcal{M}$,

where the supremum is taken over all partitions $\Pi$ of $I$ into a finite number of disjoint measurable subsets. By analogy with basis pursuit, generalized minimal extrapolation is the process of reconstructing a target measure $\sigma$ from the observation $\mathcal{K}_{n}(\sigma)=(c_{0}(\sigma),\dotsc,c_{n}(\sigma))$ of its first $n+1$ generalized moments $c_{k}(\sigma)$ by finding a solution of the problem

Let us emphasize that generalized minimal extrapolation looks for a minimizer among all signed measures on $I$. Nevertheless, the target measure $\sigma$ is assumed to be of extrema Jordan type.

Let us define more precisely what we understand by the Jordan support family $\varUpsilon$.

We say that a signed measure $\mu$ is of extrema Jordan type $($with respect to a family $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\})$ if and only if its Jordan decomposition $\mu=\mu^{+}-\mu^{-}$ satisfies

$P$ denotes any linear combination of elements of $\mathcal{F}$,

$P$ is not constant and $\left\lVert P\right\lVert_{\infty}\leq 1$,

$E^{+}_{P}$ $($resp. $E^{-}_{P})$ is the set of all points $x_{i}$ such that $P(x_{i})=1$ $($resp. $P(x_{i})=-1)$.

In the following, we give some examples of extrema Jordan type measures with respect to the family

For the sake of readability, let $n=2m$ be an even integer. We present three important examples.

The nonnegative measures whose support has size $s$ not greater than $n/2$ are extrema Jordan type measures. Indeed, let $\sigma$ be a nonnegative measure and $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}$ be its support. Set

Then, for a sufficiently small value of the parameter $c$, the polynomial $P$ has supremum norm not greater than $1$. The existence of such a polynomial shows that the measure $\sigma$ is an extrema Jordan type measure.

In Section 2 we extend this notion to any homogeneous $M$-system.

The $k$-th Chebyshev polynomial of the first order is defined by

It is well known that it has supremum norm not greater than $1$, and that

E^{+}_{T_{k}}=\big{\{}\cos(2l\pi/k),\ l=0,\dotsc,\big{\lfloor}\frac{k}{2}\big{\rfloor}\big{\}},

E^{-}_{T_{k}}=\big{\{}\cos((2l+1)\pi/k),\ l=0,\dotsc,\big{\lfloor}\frac{k}{2}\big{\rfloor}\big{\}},

whenever $k>0$. Then, any measure $\sigma$ such that

for some $0<k\leq n$, is an extrema Jordan type measure.

Further examples are presented in Section 3.

Let $\Delta$ be a positive real and $S_{\Delta}$ be the set of all pairs $(S^{+},S^{-})$ of subsets of $$ such that

In Lemma 4.2, we prove that, for all $(S^{+},S^{-})\in S_{\Delta}$, there exists a polynomial $P_{(S^{+},S^{-})}$ such that

$P_{(S^{+},S^{-})}$ has degree $n$ not greater than a bound depending only on $\Delta$,

$P_{(S^{+},S^{-})}$ is equal to $1$ on the set $S^{+}$,

$P_{(S^{+},S^{-})}$ is equal to $-1$ on the set $S^{-}$,

and $\lVert{P_{(S^{+},S^{-})}}\lVert_{\infty}\leq 1$.

This shows that any measure $\sigma$ with Jordan support included in $S_{\Delta}$ is an extrema Jordan type measure.

In this paper, we give exact reconstruction results for these three kinds of extrema Jordan type measures. In fact, our results extend to others families $\mathcal{F}$. Roughly, they can be stated as follows:

Assume that $\mathcal{F}$ is a homogeneous $M$-system (see 2.1.3). Theorem 2.1 shows that any nonnegative measure $\sigma$ is the unique solution of generalized minimal extrapolation given the observation $\mathcal{K}_{n}(\sigma)$, where $n$ is not less than twice the size of the support of $\sigma$.

Considering the standard family $\mathcal{F}_{p}^{n}=\{1,x,x^{2},\dotsc,x^{n}\}$, Proposition 4.3 shows that generalized minimal extrapolation exactly recovers any $\Delta$-spaced out type measure $\sigma$ from the observation $\mathcal{K}_{n}(\sigma)$, where $n$ is greater than a bound depending only on $\Delta$.

These results are closely related to standard results of basis pursuit [Don06]. In fact, further analogies with compressed sensing can be emphasized.

Analogy with compressed sensing

Our estimator follows the aura of the recent breakthroughs [CDS98, CRT06a] in compressed sensing.

Let $\sigma$ be an extrema Jordan type measure. Then $\sigma$ is a point of contact between the ball of radius $\|\sigma\|_{TV}$ and the affine space $\{\mu\in\mathcal{M},\ \mathcal{K}_{n}(\mu)=\mathcal{K}_{n}(\sigma)\}$, where $n$ is greater than a bound depending only on the structure of the Jordan support of $\sigma$. For instance, in the nonnegative measure case, if $\sigma$ has support of size at most $s$, then $n=2s$ suffices $($see Theorem 2.1$)$.

Organization

This paper falls into four parts. The next section introduces generalized dual polynomials and shows that exact recovery can be understood in terms of an interpolation problem. Section 2 studies the exact reconstruction of nonnegative measures, and gives explicit construction of design matrices for basis pursuit. Section 3 focuses on generalized Chebyshev polynomials and shows that it is possible to reconstruct signed measures from very few generalized moments. The last section uncovers a property related to the nullspace property of compressed sensing.

Generalized dual polynomials

In this section we introduce generalized dual polynomial. In particular we are concerned with a sufficient condition that guarantees the exact reconstruction of the measure $\sigma$. In fact, this condition relies on an interpolation problem.

An insight into exact reconstruction is given by Lemma 1.1. Roughly, the existence of a generalized dual polynomial is a sufficient condition for the exact reconstruction of a signed measure with finite support.

Let $n$ be a positive integer. Let $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}\subset I$ be a subset of size $s$ and $(\varepsilon_{1},\dotsc,\varepsilon_{s})\in\{\pm 1\}^{s}$. If there exists a linear combination $P=\sum_{k=0}^{n}a_{k}u_{k}$ such that

$P(x_{i})=\varepsilon_{i},\ \forall\,i=1,\dotsc,s$,

$\left|P(x)\right|<1,\ \forall x\in\setminus\mathcal{S}$,

The linear combination $P$ considered in the Lemma 1.1 is called a generalized dual polynomial. This naming is inherited from the original article [CRT06a] of Candès, Tao and Romberg, and the dual certificate named by Candès and Plan [CP10].

2. Reconstruction of a cone

Let us denote this set by $\mathcal{C}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$. It is exactly the cone defined by

Thus the existence of $P$ implies the exact reconstruction of all measures in this cone. The cone $\mathcal{C}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$ is the conic span of an $\textstyle(s-1)$-dimensional face of the $TV$-unit ball, that is

Furthermore, the affine space $\{\mu,\ \mathcal{K}_{n}(\mu)=\mathcal{K}_{n}(\sigma)\}$ is tangent to the $TV$-unit ball at any point $\sigma\in\mathcal{F}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$, as shown in the following remark.

From a convex optimization point of view, the dual certificates [CP10] and the generalized dual polynomials are deeply related: the existence of a generalized dual polynomial $P$ implies that, for all $\sigma\in\mathcal{F}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$, a subgradient $\Phi_{P}$ of the $TV$-norm at the point $\sigma$ is perpendicular to the set of the feasible points, that is

where $\ker$ denotes the nullspace. A proof of this remark can be found in A.2.

3. On condition (i) in Lemma 1.1

Obviously, when $u_{k}=x^{k}$ for $k=0,1,\dotsc,n$, conditions $(ii)$ and $(iii)$ imply that $n\geq s$ and so condition $(i)$. Nevertheless, this implication is not true for a general set of functions $\{u_{0},u_{1},\dotsc,u_{n}\}$. Moreover, Lemma 1.1 can fail if condition $(i)$ is not satisfied. For example, set $n=0$ and consider a continuous function $u_{0}$ satisfying the two conditions $(ii)$ and $(iii)$. In this case, if the target $\sigma$ belongs to $\mathcal{F}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$ (where $x_{1},\dotsc,x_{s}$ and $\varepsilon_{1},\dotsc,\varepsilon_{s}$ are given by $(ii)$ and $(iii)$), then every measure \mu\in\mathcal{F}\big{(}x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s}\big{)} is a solution of generalized minimal extrapolation given the observation $\mathcal{K}_{0}(\sigma)$. Indeed,

for all \mu\in\mathcal{F}\big{(}x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s}\big{)}. This example shows that condition $(i)$ is necessary. Reading the proof A.1, conditions $(ii)$ and $(iii)$ ensure that the solutions to generalized minimal extrapolation belong to the cone $\mathcal{C}(x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s})$, whereas condition $(i)$ gives uniqueness.

4. The extrema Jordan type measures

Lemma 1.1 shows that Definition 1 is well-founded. In fact, we have the the following corollary.

Let $\sigma$ be an extrema Jordan type measure. Then the measure $\sigma$ is a solution to generalized minimal extrapolation given the observation $\mathcal{K}_{n}(\sigma)$.

Furthermore, if the Vandermonde system given by $(i)$ in Lemma 1.1 has full column rank $($where $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}$ denotes the support of $\sigma)$, then the measure $\sigma$ is the unique solution to generalized minimal extrapolation given the observation $\mathcal{K}_{n}(\sigma)$.

This corollary shows that the "extrema Jordan type" notion is appropriate to exact reconstruction using generalized minimal extrapolation.

Exact reconstruction of the nonnegative measures

Denote by $\{u_{0},u_{1},\dotsc,u_{k}\}$ a set of continuous real (or complex) functions on $\overline{I}$. This set is a $T$-system of degree $k$ if and only if every generalized polynomial

where $(a_{0},\dotsc,a_{k})\neq(0,\dotsc,0)$, has at most $k$ zeros in $I$.

This definition is equivalent to each of the two following conditions:

For all $x_{0},\dotsc,x_{k}$ distinct elements of $I$, generalized Vandermonde system

1.2. M𝑀M-systems

We say that the family $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ is an $M$-system if and only if it is a $T$-system of degree $k$ for all $0\leq k\leq n$. Actually, $M$-systems are common objects (see [KN77]). We mention some examples below.

In this paper, we are concerned with target measures on $I=$. Usually $M$-systems are defined on general Hausdorff spaces (see [BEZ94] for instance). For the sake of readability, we present examples with different values of $I$. In each case, our results easily extend to target measures with finite support included in the corresponding $I$. As usual, if not specified, the set $I$ is assumed to be $$.

The family $\mathcal{F}_{p}=\{1,x,x^{2},\dotsc\}$ is an $M$-system. The real polynomials give the standard moments.

Let $0<\alpha_{1}<\alpha_{2}<\dotsb$ be any real numbers. The family $\mathcal{F}_{m}=\{1,x^{\alpha_{1}},x^{\alpha_{2}},\dotsc\}$ is an $M$-system on $I=[0,+\infty)$.

The family $\mathcal{F}_{\cos{}}=\left\{1,\cos(\pi x),\cos(2\pi x),\dotsc\right\}$ is an $M$-system on $I=$.

The family \mathcal{F}_{s}=\big{\{}\frac{1}{z_{1}-x},\frac{1}{z_{2}-x},\dotsc\big{\}}, where none of the $z_{k}$’s belongs to $$, is an$M$-system. The corresponding moments are the Stieltjes transformation$S_{\sigma}(z_{k})$of$\sigma$, namely

The family $\mathcal{F}_{l}=\left\{1,\exp(-x),\exp(-2x),\dotsc\right\}$ is an $M$-system. The moments are the Laplace transform $\mathcal{L}\sigma$ at integer points, namely

A broad variety of common families can be considered in our framework. The above list is not meant to be exhaustive.

Consider the family \mathcal{F}_{s}=\big{\{}\frac{1}{z_{0}-x},\frac{1}{z_{1}-x},\dotsc\big{\}}. Note that no linear combination of its elements gives the constant function $1$. Thus the constant function $1$ is not a generalized polynomial of this system. To treat such cases, we introduce homogeneous $M$-systems.

1.3. Homogeneous M𝑀M-systems

From any $M$-system we can always construct a homogeneous $M$-system. Indeed, let $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ be an $M$-system. In particular the family $\mathcal{F}$ is a $T$-system of order . Thus the continuous function $u_{0}$ does not vanish in $$. In fact the family$\{1,\frac{u_{1}}{u_{0}},\frac{u_{2}}{u_{0}},\dotsc,\frac{u_{n}}{u_{0}}\}$is a homogeneous$M$-system.

All the previous examples of $M$-systems (see 2.1.2) are homogeneous, even Stieltjes transformation:

Using homogeneous $M$-systems, we show that one can exactly recover all nonnegative measures from a few generalized moments.

2. An important theorem

Let $\mathcal{F}$ be an homogeneous $M$-system on $I$. Consider a nonnegative measure $\sigma$ with finite support included in $I$. Then the measure $\sigma$ is the unique solution to generalized minimal extrapolation given observation $\mathcal{K}_{n}(\sigma)$, where $n$ is not less than twice the size of the support of $\sigma$.

The complete proof can be found in B.1 but some key points from the theory of approximation are presented in 2.2.1. For further insights about Markov systems, we recommend the books [KN77, KS66]. ∎

An important property of $M$-systems is the existence of a nonnegative generalized polynomial that vanishes exactly at a prescribed set of points $\{t_{1},\dotsc,t_{m}\}$, where $t_{i}\in I$ for all $i=1,\dotsc,m$. Indeed, define the index as

where $\chi(t)=2$ if $t$ belongs to $\mathring{I}$ (the interior of $I$) and $1$ otherwise. The next lemma guarantees the existence of nonnegative generalized polynomials.

A proof of this lemma is in [KN77]. Note that this lemma holds for all $M$-systems. However our main theorem needs a homogeneous $M$-system.

2.2. Is homogeneous necessary?

If one considers non-homogeneous $M$-systems then it is possible to give counterexamples that go against Theorem 2.1 for all $n\geq 2s$. Indeed, we have the next result.

Let $\sigma$ be a nonnegative measure supported by $s$ points. Let $n$ be an integer such that $n\geq 2s$. Then there exists an $M$-system $\mathcal{F}$ and a measure $\mu\in\mathcal{M}$ such that $\mathcal{K}_{n}(\sigma)=\mathcal{K}_{n}(\mu)$ and $\left\lVert\mu\right\lVert_{TV}<\left\lVert\sigma\right\lVert_{TV}$.

Theorem 2.1 gives us the opportunity to build a large family of deterministic matrices for compressed sensing in the case of nonnegative signals.

3. Deterministic matrices for compressed sensing

The heart of this article lies in the next theorem. It gives deterministic matrices for compressed sensing. We begin with some state-of-the-art results in compressed sensing. In the following, $p$ denotes the number of predictors (or, from a signal processing view point, the length of the signal).

The deterministic result holds for large values of $s$, $n$ and $p$. For readability we do not specify the sense of large here. The reader may find an abundant literature in the respective references (see for example [BGI+08, Don06]).

Considering nonnegative sparse vectors, it is possible to drop the bound on $n$ to

Unlike the above examples, this result holds for all values of the parameters (as soon as $n\geq 2s+1$). In addition it give explicit design matrices for basis pursuit. Last but not least, this bound on $n$ does not depend on $p$. In special cases, this result has been previously developed in [DJHS92, Fuc96, DT05, DT10]. Using Theorem 2.1, it is possible to provide a generalization of this result to a broad range of measurement matrices:

Let $\{1,u_{1},\dotsc,u_{n}\}$ be a homogeneous $M$-system on $I$. Let $t_{1},\dotsc,t_{p}$ be distinct reals of $I$. Let $A$ be generalized Vandermonde system defined by

The purely analytical components of this result are tractable back to the theory of neighborly polytopes (see for instance [DT05]) and in some sense trace to the theory of moment problems which essentially follows from Carathéodory work [Car07, Car11]. Other relevant work includes [KS53, Der56, Stu88]. This list is not meant to be exhaustive.

Although the predictors could be highly correlated, basis pursuit exactly recovers the target vector $x_{0}$. Of course, this result is theoretical. In practice, the sensing matrix $A$ can be very ill-conditioned. In this case, basis pursuit behaves poorly.

Our numerical experiments illustrate Theorem 2.4. They are of the following form:

Choose constants $s$ (sparsity), $n$ (number of known moments), and $p$ (length of the vector). Choose the family $\mathcal{F}$ (cosine, polynomial, Laplace, Stieltjes,…).

Select the subset $\mathcal{S}$ (of size $s$) uniformly at random.

Randomly generate an $s$-sparse vector $x_{0}$ of support $\mathcal{S}$ whose nonzero entries have the chi-square distribution with $1$ degree of freedom.

The entries of the target signal are distributed according to chi-square distribution with $1$ degree of freedom. We chose this distribution to ensure that the entries are nonnegative. Let us emphasize that the actual values of $x_{0}$ can be arbitrary; only the sign matters. The result remains the same if we take the nonzero entries to be $1$, say.

Let us denote $K:t\mapsto(1,u_{1}(t),\dotsc,u_{n}(t))$. The columns of $A$ are the values of this map at points $t_{1},\dotsc,t_{p}$. For large $p$, the vectors $K(t_{i})$ can be highly correlated. In fact, the matrix $A$ can be ill-conditioned. To avoid such a case, we chose a family such that the map $K$ has a large derivative. It appears that the cosine family gives very good numerical results (see Figure 1).

Choose $p$ (length of the vector) and $N$ (number of numerical experiments).

Note that all experiments were done for $n=2s+1$. This is the smallest value of $n$ such that Theorem 2.3 holds.

Exact reconstruction for generalized Chebyshev measures

In the context of $M$-systems we can exhibit some very particular dual polynomials. The global extrema of these polynomials gives families of support for which results of Lemma 1.1 hold.

First, consider the $(n+1)$-dimensional cosine system

for $k=1,\dotsc,n$, satisfy $\left\lVert P_{k}\right\lVert_{\infty}\leq 1$ and $P_{k}(l/k)=(-1)^{l}$, for $l=0,1,\dotsc,(k-1)$. According to Definition 1, let us denote

E^{+}_{P_{k}}:=\big{\{}2l/k\ |\ l=0,\dotsc,\lfloor\frac{k-1}{2}\rfloor\big{\}},

E^{-}_{P_{k}}:=\big{\{}(2l-1)/k\ |\ l=1,\dotsc,\lfloor\frac{k}{2}\rfloor\big{\}}.

The corollary that follows Lemma 1.1 asserts the following result.

Consider a signed measure $\sigma$ having Jordan support $(\mathcal{S}^{+},\mathcal{S}^{-})$ such that $\mathcal{S}^{+}\subset E^{+}_{P_{k}}$ and $\mathcal{S}^{-}\subset E^{-}_{P_{k}}$, for some $1\leq k\leq n$. Then the measure $\sigma$ can be exactly reconstructed from the observation of

the system of function $(1,\cos(\pi x),\dotsc,\cos(n\pi x))$ can be push-forward to the system of functions $(1,T_{1}(x),\dotsc,T_{n}(x))$, where $T_{k}(x)$ is the so-called Chebyshev polynomial of the first kind of order $k$, $k=1,\dotsc,n$ (see 3.2).

The characteristic function

By the same token, consider the complex valued $M$-system defined by

on $I=[0,2)$. In this case, one can check that

Hence Lemma 1.1 can be applied. It yields the following:

where $\varphi_{\sigma}(k\pi)$ has been defined in the previous section $($see 2.1.2$)$.

Note that the study of basis pursuit with this kind of trigonometric moments has been considered in the pioneering work of Donoho and Stark [DS89].

2. Chebyshev polynomials

As mentioned in the introduction, the $k$-th Chebyshev polynomial of the first order is defined by

We give some well known properties of Chebyshev polynomials. The $k$-th Chebyshev polynomial satisfies the equioscillation property on $$. In fact, there exist$k+1$points$\zeta_{i}=\cos(\pi i/k)$with$1=\zeta_{0}>\zeta_{1}>\dotsb>\zeta_{k}=-1$ such that

where the supremum norm is taken over $$. Moreover, the Chebyshev polynomial$T_{k}$ satisfies the following extremal property.

These two properties, namely the equioscillation property and the extremal property, will be useful to us when we define generalized Chebyshev polynomial.

Using Lemma 1.1 we uncover an exact reconstruction result. Consider the family

E^{+}_{T_{k}}=\big{\{}\cos(2l\pi/k),\ l=0,\dotsc,\big{\lfloor}\frac{k}{2}\big{\rfloor}\big{\}},

E^{-}_{T_{k}}=\big{\{}\cos((2l+1)\pi/k),\ l=0,\dotsc,\big{\lfloor}\frac{k}{2}\big{\rfloor}\big{\}}.

Note that this result is restrictive in the location of the support points, they are not sparse in the usual sense, because they must be precisely located. Nevertheless, it can be extended to any $M$-systems with the help of generalized Chebyshev polynomials.

3. Generalized Chebyshev polynomials

Following [BE95], we define generalized Chebyshev polynomials as follows. Let $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ be an $M$-system on $I$.

where $1\leq k\leq n$, is defined by the following three properties:

there exists $x_{0}<x_{1}<\dotsb<x_{k}$ such that

The existence and the uniqueness of such $\mathfrak{T}_{k}$ is proved in [BE95]. Moreover, the following theorem shows that the extremal property implies the equioscillation property (5).

The $k$-th generalized Chebyshev polynomial $\mathfrak{T}_{k}$ exists and can be written as

Generalized Chebyshev polynomials give a new family of extrema Jordan type measures (see Definition 1). The corresponding target measures are named Chebyshev measures.

3.2. Exact reconstruction of Chebyshev measures

Considering the equioscillation property (5), set

A direct consequence of the last definition is the following proposition.

As far as we know, it is difficult to give the corresponding generalized Chebyshev polynomials for a given family $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$. Nevertheless, Borwein, Erdélyi, and Zhang [BEZ94] gives the explicit form of $\mathfrak{T}_{k}$ for rational spaces (i.e. the Stieltjes transformation in our framework). See also [DS89, HSS96] for some applications in optimal design.

3.3. Construction of Chebyshev polynomials for Stieltjes transformation

We consider the case of Stieltjes transformation described in Section 2. In this case, Chebyshev polynomials $\mathfrak{T}_{k}$ can be precisely described. Consider homogeneous $M$-system on $$ defined by

Reproducing [BE95], we can construct generalized Chebyshev polynomials of the first kind. It yields

where $z$ is uniquely defined by $x=\frac{1}{2}(z+z^{-1})$ and $\left|z\right|<1$, and $f_{k}$ is a known analytic function in a neighborhood of the closed unit disk. Moreover this analytic function can be expressed in terms of only $(z_{i})_{i=1}^{k}$. We refer to [BE95] for further details.

The nullspace property for measures

In this section we consider any countable family $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ of continuous functions on $I$. In particular we do not assume that $\mathcal{F}$ is a non-homogeneous $M$-system. We aim at deriving a sufficient condition for exact reconstruction of signed measures. More precisely, we are concerned with giving a related property to the nullspace property [CDD09] of compressed sensing.

In this section, we show that the same property holds for generalized minimal extrapolation. According to the compressed sensing literature, we keep the same name for this related property.

2. The nullspace property for generalized minimal extrapolation

Let $\mu\in\mathcal{M}$ and $S=\{x_{1},\dotsc,x_{s}\}$ be a finite subset of $I$. Define $\Delta_{S}=\sum_{i=1}^{s}\delta_{x_{i}}$ as the Dirac comb with support $S$. The Lebesgue decomposition of $\mu$ with respect to $\Delta_{S}$ gives

where $\mu_{S}$ is a discrete measure whose support is included in $S$, and $\mu_{S^{c}}$ is a measure whose support is included in $S^{c}:=I\setminus S$.

2.2. The nullspace property with respect to a Jordan support family

First, as in the standard compressed sensing context [CDD09], we define the nullspace property with respect to a Jordan support family $\varUpsilon$. This property is only a sufficient condition for exact reconstruction of finite measure; see Proposition 4.1.

We say that the generalized moment morphism $\mathcal{K}_{n}$ satisfies the nullspace property with respect to a Jordan support family $\varUpsilon$ if and only if it satisfies the following property. For all nonzero measures $\mu$ in the nullspace of $\mathcal{K}_{n}$, and for all $(\mathcal{S}^{+},\mathcal{S}^{-})\in\varUpsilon$,

where $\mathcal{S}=\mathcal{S}^{+}\cup\mathcal{S}^{-}$.

— The weak nullspace property states as follows: For all nonzero measures $\mu$ in the nullspace of $\mathcal{K}_{n}$, and for all $(\mathcal{S}^{+},\mathcal{S}^{-})\in\varUpsilon$,

where $\mathcal{S}=\mathcal{S}^{+}\cup\mathcal{S}^{-}$.

Given a nonzero measure $\mu$ in the nullspace of $\mathcal{K}_{n}$, this property means that more than half of the total variation of $\mu$ cannot be concentrated on a small subset. The nullspace property is a key to exact reconstruction as shown in the following proposition.

As far as we know, it is difficult to check the nullspace property. In the following, we give an example such that the weak nullspace property is satisfied.

3. The spaced out interpolation

We recall that $S_{\Delta}$ is the set of all pairs $(S^{+},S^{-})$ of subsets of $I=$ such that

The next lemma shows that if $\Delta$ is large enough then there exists a polynomial of degree $n$, with supremum norm not greater than $1$, that interpolates $1$ on the set $\mathcal{S}^{+}$ and $-1$ on the set $\mathcal{S}^{-}$.

For all $(S^{+},S^{-})\in S_{\Delta}$, there exists a polynomial $P_{(S^{+},S^{-})}$ such that

$P_{(S^{+},S^{-})}$ has degree $n$ not greater than $(2/\sqrt{\pi})\,(\sqrt{e}/\Delta)^{5/2+1/\Delta}$,

$P_{(S^{+},S^{-})}$ is equal to $1$ on the set $S^{+}$,

$P_{(S^{+},S^{-})}$ is equal to $-1$ on the set $S^{-}$,

and $\lVert{P_{(S^{+},S^{-})}}\lVert_{\infty}\leq 1$ over $I$.

This upper bound is meant to show that one can interpolate any sign sequence on $S_{\Delta}$. Let us emphasize that this result is far from being sharp. Considering $L_{2}$-minimizing polynomials under fitting constraint, the authors of the present paper believe that one can greatly improve the upper bound of Lemma 4.2. Indeed, our numerical experiments are in complete agreement with this comment. Invoking Lemma 1.1, Lemma 4.2 gives the next proposition.

Let $\Delta$ be a positive real. If $n\geq(2/\sqrt{\pi})\,(\sqrt{e}/\Delta)^{5/2+1/\Delta}$ then $\mathcal{K}_{n}$ satisfies the weak nullspace property with respect to $S_{\Delta}$.

The bound $(2/\sqrt{\pi})\,(\sqrt{e}/\Delta)^{5/2+1/\Delta}$ can be considerably improved in actual practice. The following numerical experiment shows that this bound can be greatly lowered.

In our experiments we consider the values $\Delta=1/15,1/20,\dotsc,1/55$. According to Proposition 4.3, the corresponding values of $n$ range from $10^{19}$ to $10^{59}$. In our experiments, we find that $n=80$ suffices.

Acknowledgements: The authors would like to thank Jean Paul Calvi and Viet Hung Pham for fruitful comments. We also thank anonymous referees for their careful reviews and their interesting suggestions.

Appendix A Proofs of Section 1.

according to the Lebesgue decomposition (7). Since $\left\lVert P\right\lVert_{\infty}=1$, we have

which is a contradiction. We deduce that $\left\lVert\nu_{\Omega_{k}}\right\lVert_{TV}=0$, for all $k>0$. The equality $\nu=0$ follows with ${\mathcal{S}^{c}}=\cup_{k>0}\Omega_{k}$ . ∎

This lemma shows that $\sigma^{\star}$ is a discrete measure with its support included in $\mathcal{S}$. In this case, the moment constraint $\mathcal{K}_{n}(\sigma^{\star}-\sigma)=0$ can be written as a generalized Vandermonde system,

From condition $(i)$, we deduce that the generalized Vandermonde system is injective. $\square$

A.2. Proof of the remark in Section Remark

Let $\sigma$ belong to \mathcal{F}\big{(}x_{1},\varepsilon_{1},\dotsc,x_{s},\varepsilon_{s}\big{)}. Consider the linear functional,

where $f$ denotes a continuous bounded function. By definition, any subgradient $\Phi_{f}$ of the $TV$-norm at point $\sigma$ satisfies, for all measures $\mu\in\mathcal{M}$,

Appendix B Proofs of Section 2

The proof essentially relies on Lemma 1.1. Let $s$ be an integer. Let $\sigma$ be a nonnegative measure. Let $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}\subset I$ be its support. The next lemma shows the existence of a generalized dual polynomial.

$\left|P(x)\right|<1$ for all $x\notin\{x_{1},\dotsc,x_{s}\}$.

Since $Q$ is continuous on the compact set $\overline{I}$, it is bounded and there exists a real $c$ such that $\left\lVert Q\right\lVert_{\infty}<1/c$. The generalized polynomial $P=1-cQ$ is the expected generalized polynomial. ∎

Using Lemma B.1, it yields that there exists a generalized dual polynomial, of degree at most $n=2s$, which interpolates the value $1$ at points $\{x_{1},\dotsc,x_{s}\}$.

Since $\mathcal{F}=\{u_{0},u_{1},\dotsc,u_{n}\}$ is a $T$-system, the Vandermonde system given by $(i)$ in Lemma 1.1 has full column rank.

Since $\mathcal{F}$ is a homogeneous $M$-system, the constant function $1$ is a generalized polynomial. Note that the linear combination $P=1-cQ$ is a generalized polynomial because $1$ is a generalized polynomial. This assumption is essential $($see 2.2.2$)$.

B.2. Proof of Proposition 2.3

Let $\sigma=\sum_{i=1}^{s}\sigma_{i}\delta_{x_{i}}$ be a nonnegative measure. Let $\mathcal{S}=\{x_{1},\dotsc,x_{s}\}$ be its support. Let $n$ be an integer such that $n\geq 2s$.

$\nu=\displaystyle\sum_{i=1}^{n+1}\nu_{i}\delta_{t_{i}}$,

Step 2:

Consider a positive continuous function $u_{0}$ such that

Set $\mathcal{F}=\{u_{0},u_{0}\,u_{1},u_{0}\,u_{2},\dotsc\}$. Obviously, $\mathcal{F}$ is a non-homogeneous $M$-system. As usual, let $\mathcal{K}_{n}$ denote the generalized moment morphism of order $n$ derived from the family $\mathcal{F}$.

Last step:

Set $\mu=r\,\nu$. An easy calculation gives $\mathcal{K}_{n}(\sigma)=\mathcal{K}_{n}(\mu)$. Note that

B.3. Proof of Theorem 2.4

Set $\mathcal{T}=\{t_{1},\dotsc,t_{p}\}$. Let $\mathcal{M}_{\mathcal{T}}$ denote the set of all finite measures of which support is included in $\mathcal{T}$. Let $\varTheta_{\mathcal{T}}$ be the linear map defined by

One can check that $\varTheta_{\mathcal{T}}$ is a bijective isometry. Moreover, it holds that

where $A$ is the generalized Vandermonde system defined by

Using (10) and the isometry $\varTheta_{\mathcal{T}}$, it follows that $x_{0}$ is the unique solution to the program:

Appendix C Proofs of Section 4

where $\mathcal{S}$ denotes the support of $\sigma$. Suppose that $\mu\neq 0$. The nullspace property yields that the measure $\mu$ satisfies inequality (8). We deduce $\left\lVert\sigma^{\star}\right\lVert_{TV}>\left\lVert\sigma\right\lVert_{TV}$, which is a contradiction. Thus $\mu=0$ and $\sigma^{\star}=\sigma$. $\square$

C.2. Proof of Lemma 4.2

For sake of readability, we sketch the proof here. Let $(S^{+},S^{-})\in S_{\Delta}$. Set $S=S^{+}\cup S^{-}=\{x_{1},\dotsc,x_{s}\}$. Consider the Lagrange interpolation polynomials

for $1\leq k\leq s$. One can bound the supremum norm of $l_{k}$ over $$ by

where $L(\Delta)$ is an upper bound that depends only on $\Delta$. Consider the $m$-th Chebyshev polynomial of the first order $T_{m}(x)=\cos(m\arccos(x))$, for all $x\in$. For a sufficiently large value of $m$, there exist $2s$ extrema $\zeta_{i}$ of $T_{m}$ such that $\left|\zeta_{i}\right|\leq 1/(sL(\Delta))$. Interpolating values $\zeta_{i}$ at point $x_{k}$, we build the expected polynomial $P$. We find that the polynomial $P$ has degree not greater than

C.3. Proof of Proposition 4.3

Let $\mu$ be a nonzero measure in the nullspace of $\mathcal{K}_{n}$ and $(\mathcal{A},\mathcal{B})$ be in $S_{\Delta}$. Let $\mathcal{S}$ be equal to $\mathcal{A}\cup\mathcal{B}$. Let $\mathcal{S}^{+}$ (resp. $\mathcal{S}^{-}$) be the set of points $x$ in $\mathcal{S}$ such that the $\mu$-weight at point $x$ is nonnegative (resp. negative). Observe that $\mathcal{S}=\mathcal{S}^{+}\cup\mathcal{S}^{-}$ and $(\mathcal{S}^{+},\mathcal{S}^{-})\in S_{\Delta}$. From Lemma 4.2, there exists $P_{(S^{+},S^{-})}$ of degree not greater than $n$ such that $P_{(S^{+},S^{-})}$ is equal to $1$ on $S^{+}$, $-1$ on $S^{-}$, and $\lVert{P_{(S^{+},S^{-})}}\lVert_{\infty}\leq 1$. It yields

Appendix D Numerical Experiments

Note that some coefficients can be badly estimated (for instance when $s=50$ and $n=101$). This might be due to the fact that we consider the limit case $n=2s+1$. Nevertheless, this is not the case when we have very few coefficients ($s=10$ and $n=21$) or a large number of moments ($s=150$ and $n=301$). As a general rule, we observe faithful reconstruction.

References