# Generalized Polar Approximation for translation-invariant dictionaries

Frédéric Champagnat, Cédric Herzet

<figure><img src="image_1.png" /></figure>

## To cite this version:

Frédéric Champagnat, Cédric Herzet. Generalized Polar Approximation for translation-invariant dictionaries. ICASSP 2020, May 2020, Barcelone, Spain. hal-04708369

HAL Id: hal-04708369

https://hal.science/hal-04708369v1

Submitted on 24 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
GENERALIZED POLAR APPROXIMATION
FOR TRANSLATION-INVARIANT DICTIONARIES

F. Champagnat* and C. Herzet†

*ONERA, The French Aerospace Lab, BP 80100 91123, Palaiseau Cedex, France

†INRIA Rennes-Bretagne Atlantique, Campus de Beaulieu, 35000 Rennes, France

ABSTRACT

In this paper, we address the problem of approximating the atoms of a parametric dictionary $\mathcal{A} = \{a(\theta) : \theta \in \Theta\}$. We focus on the case of translation-invariant dictionaries, where the inner product between $a(\theta)$ and $a(\theta')$ only depends on the difference $\theta - \theta'$. We propose a new family of approximations, dubbed “generalized polar approximation”, preserving the translation-invariant structure of the original dictionary while interpolating a subset of atoms $\{a(\theta_j)\}_{j=1}^J$. Interestingly, the proposed framework extends the one-dimensional “polar approximation” proposed by Ekanadham et al. in [1] to more general settings.

**Index Terms—** Sparse representations, continuous dictionaries, translation-invariant approximations, interpolating approximations.

1. INTRODUCTION

Sparse representations aim at representing a signal of interest as the linear combination of a few elements of a dictionary $\mathcal{A}$. Recently, this problem as been reformulated in a “continuous” setting, where the elements of $\mathcal{A}$ are continuously indexed by some parameter $\theta$:

$$ \mathcal{A} = \{a(\theta) \in \mathcal{H} : \theta \in \Theta\} \quad (1) $$

where $\Theta$ is a pave of $\mathbb{R}^d$, $\mathcal{H}$ is a Hilbert space over the real field $\mathbb{R}$ with inner product $\langle \cdot, \cdot \rangle$ and induced norm $\|\cdot\|$, and $a(\cdot)$ some function from $\Theta$ to $\mathcal{H}$, see e.g., [2]. In this paper, we adopt the common hypothesis that $\|a(\theta)\| = 1 \forall \theta \in \Theta$.

Continuous dictionaries contain an infinite uncountable number of elements and induce therefore new difficulties. One line of thought which has been proposed in several contributions [1, 3, 4] to deal with the infinite-dimensional nature of continuous dictionaries is to resort to “low-rank” approximation of $a(\theta)$. More formally, the idea consists in approximating the elements of $\mathcal{A}$ as linear combinations of a

few vectors $\{v_k\}_{k=0}^K$:

$$ \hat{a}(\theta) \triangleq v_0 + \sum_{k=1}^{K} v_k c_k(\theta) \quad (2) $$

for some functions $\{c_k : \Theta \to \mathbb{R}\}_{k=0}^K$.

This approach was for example used in [1] and [3] to transform “continuous” sparse-representation problems into approximate (but tractable) finite-dimensional ones. The quality of the approximation obtain with this strategy obviously depends on the choice of the vectors $\{v_k\}_{k=0}^K$ and functions $\{c_k\}_{k=1}^K$. Several options was considered in [1,3,4]. In [1], the authors introduced the “Taylor” and “polar” approximations: the former is based on a Taylor decomposition of $a(\theta)$; the latter is constructed so that $\hat{a}(\theta)$ has a unit norm $\forall \theta \in \Theta$ and interpolates $a(\theta)$ for some $\{\theta_k\}_{k=0}^K$. In [3], the authors suggested to use a singular-value decomposition of $a(\theta)$ to identify the approximation subspace minimizing the projection error in a $\|\cdot\|$-sense. In [4], the authors emphasized that approximations of the form (2) may be of interest to solve the so-called “atom selection” problem:

$$ \theta^* = \arg\max_{\theta \in \Theta} \langle a(\theta), r \rangle \quad \text{for some } r \in \mathcal{H}, \quad (3) $$

which is central in many sparse representation algorithms operating on continuous dictionaries.<fnref n="1" /> In particular, replacing $a(\theta)$ by its approximation (2) in (3) leads to

$$ \hat{\theta}^* = \arg\max_{\theta \in \Theta} \sum_{k=1}^{K} \langle v_k, r \rangle c_k(\theta), \quad (4) $$

which may be easier to solve than (3) depending on the choice of the functions $\{c_k : \Theta \to \mathbb{R}\}_{k=0}^K$. For example, when $d = 1$, problem (4) with an orthogonal family $\{v_k\}_{k=0}^2$ and the following definitions

$$ c_0(\theta) = 1, \quad c_1(\theta) = \cos(\omega\theta), \quad c_2(\theta) = \sin(\omega\theta), $$

<footnote n="1">¹Problem (3) for example appears in the resolution of the BLASSO problem via conditional gradient methods [2, 5] or the in the implementation of “Orthogonal Matching Pursuit” [6].</footnote>

<footnote>The authors thank the ANR (ANR-15-CE23-0021) for its support.</footnote>
$\omega \in \mathbb{R}$, admits a simple closed-form solution, see [4, Lemma 1]. Interestingly, this type of decomposition occurs in the polar approximation introduced in [1].

Despite its nice properties, the polar approximation was introduced for the particular case $d = 1$ and $K = 3$. In this paper, we propose a generalization of this approximation to more general settings. We focus on the case of “translation-invariant” dictionaries, that is:

$$ \langle a(\theta), a(\theta') \rangle = \langle a(\theta - \tau), a(\theta' - \tau) \rangle, \quad (5) $$

$\forall \theta, \theta' \in \Theta$ and $\tau \in \mathbb{R}^d$ such that $\theta - \tau, \theta' - \tau \in \Theta$. We emphasize in Section 2 that the preservation of the translation invariance and the interpolation of some elements of $\mathcal{A}$ are two key features of the polar approximation proposed in [1]. We leverage these observations in Section 3 to propose a general family of approximations sharing the same desirable features. In Section 3.2 we illustrate our theoretical results on a particular example and propose a new two-dimensional polar approximation interpolating four atoms of the original dictionary. All the proofs of our results are gathered at the end of this report in Section 5.

## 2. EKANADHAM'S POLAR APPROXIMATION

In this section, we review the main ingredients of the “polar approximation” proposed in [1]. In this paper, the authors considered the case $d = 1$ and assumed that $a(\theta)$ is translation invariant (see (5)) over $\Theta = [-\frac{\Delta}{2}, \frac{\Delta}{2}]$ for some $\Delta > 0$. They suggested an approximation $\hat{a}(\theta)$ of the form

$$ \hat{a}(\theta) = v_0 + v_1 \cos(\omega\theta) + v_2 \sin(\omega\theta) \quad (6) $$

obeying the following interpolation properties:

$$ \hat{a}(\theta) = a(\theta) \quad \text{for } \theta \in \left\{-\frac{\Delta}{2}, 0, \frac{\Delta}{2}\right\}. \quad (7) $$

Interestingly, although not explicitly mentioned by the authors in [1], the unique decomposition verifying (6)-(7) must satisfy $\langle v_k, v_{k'} \rangle = 0$ for $k \neq k'$. Exploiting this property, simple calculations then show that

$$ \langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \lambda_0 + (1 - \lambda_0) \cos(\omega(\theta - \theta')) \quad (8) $$

where $\lambda_0 = \|v_0\|^2$. In other words, the dictionary approximation induced by (6)-(7) is also translation invariant.

## 3. GENERALIZED POLAR APPROXIMATION

In this section, we define a family of low-rank approximations sharing two crucial features of Ekanadham's polar approximation:

* Interpolation property:

$$ \hat{a}(\theta) = a(\theta) \quad \text{for } \theta \in \{\theta_j\}_{j=1}^J. \quad (9) $$

* Raised-cosine kernel:

$$ \langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \lambda_0 + \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\omega_{\ell}^{\mathrm{T}}(\theta - \theta')) \quad (10) $$

for some $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$.

Property (9) is the direct counterpart of (7) and impose that the approximation $\hat{a}(\theta)$ perfectly interpolates the original atoms $a(\theta)$ for some $\theta \in \{\theta_j\}_{j=1}^J$. Property (10) extends (8) to more general raised-cosine kernels. In particular, we note that (10) enforces $\hat{a}(\theta)$ to be translation invariant.

In this section we provide the main ingredients needed to construct low-rank approximations (2) verifying (9) and (10). Before proceeding, we make the following two important remarks. First, in order to simplify our exposition, we assume that $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$ are such that the left-hand side of (10) defines a positive-definite kernel. This working hypothesis has the following important implication:

**Lemma 1.** Any family of atoms $\hat{A} = \{\hat{a}(\theta) : \theta \in \Theta\}$ verifying (10) spans a 2L-dimensional affine subspace with minimum-norm vector, say $v_0$, obeying $\|v_0\|^2 = \lambda_0$.

As a consequence, simple dimensionality considerations impose that approximations of the form (2) verifying (10) must necessarily satisfy $K \ge 2L$. Hereafter, we consider the most natural case where $K = 2L$.

Second, if the family of interpolated points $\{a(\theta_j)\}_{j=1}^J$ is free, it can only be contained in an affine subspace of dimension greater than or equal to $J-1$. Hence, any approximation of the form (2) that verify (9) must satisfy $J-1 \le K$. We focus hereafter on the case $J = K$ and leave the connection between this setup and the case $J = K+1$ for future work.

In summary, we address the following question in the rest of this section:

**Main Question.** Is there an approximation of the form (2) with $K = 2L$ that interpolates a family of 2L linearly independent atoms $\{a(\theta_j)\}_{j=1}^{2L}$ and verifies (10) for some $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$?

In Section 3.1, we present necessary and sufficient conditions for such an approximation to exist (see Theorem 1) and provide closed-form expressions for $\{v_k\}_{k=0}^K$ and $\{c_k(\theta)\}_{k=1}^K$ so that the corresponding low-rank approximation (2) verifies (9)-(10) (see Theorem 2). In Section 3.2, we then illustrate our result by introducing a new two-dimensional polar approximation interpolating four atoms of the original dictionary.

### 3.1. Existence and Construction

Our first result relates the existence of a generalized polar decomposition to some constraints on the Gram matrix of the interpolated atoms $\{a(\theta_j)\}_{j=1}^{2L}$. More specifically, letting $1_{2L} \in \mathbb{R}^{2L}$ be the “all-ones” vector and

$$ \mathbf{G} \triangleq [\langle a(\theta_i), a(\theta_j) \rangle]_{i,j} \in \mathbb{R}^{2L \times 2L}, \quad (11) $$
the following result holds:

**Theorem 1.** If there exists a family of atoms (2) verifying (9)-(10) for $J = K = 2L$, then

(i) $\lambda_0 \le (\mathbf{1}_{2L}^\mathrm{T}\mathbf{G}^{-1}\mathbf{1}_{2L})^{-1}$

(ii) $\mathbf{G}(i, j) = \lambda_0 + \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\omega_{\ell}^{\mathrm{T}}(\theta_i - \theta_j)) \quad \forall i, j.$

for some $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$. Conversely, if there exists $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$ such that condition (ii) holds and condition (i) holds strictly, there exists a family of atoms (2) verifying (9)-(10) for $J = K = 2L$.

In other words, Theorem 1 provides necessary and sufficient conditions for our “Main Question” to have a positive answer. Interestingly, we see that the existence of a generalized polar decomposition is exclusively conditioned to the existence of some particular factorization of the Gram matrix $\mathbf{G}$ (see condition (i)-(ii)).

Our next theorem shows how to build a low-rank approximation $\hat{a}(\theta)$ verifying (9)-(10) if there exists some $\{\lambda_\ell\}_{\ell=0}^L$, $\{\omega_\ell\}_{\ell=1}^L$ such that condition (ii) holds and condition (i) holds strictly. This result requires the identification of one vector $\mathbf{v}_0$ verifying

$$ \|\mathbf{v}_0\|^2 = \lambda_0 \quad (12) $$

$$ \langle \mathbf{v}_0, \mathbf{a}(\theta_j) - \mathbf{v}_0 \rangle = 0 \quad \forall j = 1 \dots 2L \quad (13) $$

$$ \{\mathbf{a}(\theta_j) - \mathbf{v}_0\}_{j=1}^{2L} \text{ linearly independent.} \quad (14) $$

It is easy to see (see Lemma 4 in Section 5) that (at least) one such vector exists as soon condition (i) of Theorem 1 is strictly satisfied.

**Theorem 2.** Let $\{\lambda_\ell\}_{\ell=0}^L$ and $\{\omega_\ell\}_{\ell=1}^L$ be such that condition (ii) of Theorem 1 is satisfied and let $\mathbf{v}_0 \in \mathcal{H}$ be some vector verifying (12)-(14). Then,

$$ \hat{a}(\theta) \triangleq \mathbf{v}_0 + \sum_{k=1}^{2L} \mathbf{v}_k c_k(\theta) \quad (15) $$

with

$$ c_k(\theta) = \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\omega_{\ell}^{\mathrm{T}}(\theta - \theta_k)) \quad (16) $$

$$ \mathbf{v}_k = \sum_{\ell=1}^{2L} (\mathbf{a}(\theta_\ell) - \mathbf{v}_0) \mathbf{H}_0(k, \ell) \quad (17) $$

$$ \mathbf{H}_0 = (\langle \mathbf{a}(\theta_i) - \mathbf{v}_0, \mathbf{a}(\theta_j) - \mathbf{v}_0 \rangle)_{i,j}^{-1} \quad (18) $$

verifies (9)-(10).

Theorems 1 and 2 constitute the main building blocks of the proposed generalized polar decomposition. Theorem 1

shows that the existence of a low-rank approximation verifying (9)-(10) is tantamount to the existence of some decomposition of the Gram matrix $\mathbf{G}$. Theorem 2 provides closed-form expressions for the parameters $\{\mathbf{v}_k\}_{k=0}^{2L}$, $\{c_k\}_{k=1}^{2L}$ defining the generalized polar approximation as a function of some $\{\lambda_\ell\}_{\ell=0}^L$, $\{\omega_\ell\}_{\ell=1}^L$ verifying the conditions of Theorem 1. From a practical point of view, the most difficult part of the construction of a generalized polar approximation stands therefore in the identification of some $\{\lambda_\ell\}_{\ell=0}^L$, $\{\omega_\ell\}_{\ell=1}^L$ verifying the conditions of Theorem 1. Upon the determination of these parameters, the construction of the polar approximation directly follows from Theorem 2. In the next section, we leverage this result to propose a new two-dimensional polar approximation.

## 3.2. A Two-dimensional Polar Approximation

In this section, we particularize the general results stated in the previous section to a two-dimensional “separable” case. More particularly, we consider the setup where $\Theta = [-\frac{\Delta}{2}, \frac{\Delta}{2}]^2$ for some $\Delta > 0$. Moreover, we assume that the family of atoms to be approximated $\mathcal{A} = \{\mathbf{a}(\theta) : \theta \in \Theta\}$ has a separable translation-invariant kernel, that is

$$ \langle \mathbf{a}(\theta), \mathbf{a}(\theta') \rangle = \rho(\theta(1) - \theta'(1))\rho(\theta(2) - \theta'(2)). $$

from some positive-definite function $\rho : [-\frac{\Delta}{2}, \frac{\Delta}{2}] \to \mathbb{R}$. As mentioned at the very beginning of the paper, we also assume that the elements of $\mathcal{A}$ have unit norm, so that $\rho(0) = 1$.

We show hereafter that a generalized polar decomposition can be constructed in that particular setup. We consider the case $J = 2L = 4$ and define the interpolating points as:

$$ \theta_j = \begin{pmatrix} \pm \frac{\Delta}{2} \\ \pm \frac{\Delta}{2} \end{pmatrix}, \quad j = 1 \dots 4. $$

From Theorem 1, a low-rank decomposition of the form (2) verifying (9)-(10) exist if there exists $\{\lambda_\ell\}_{\ell=0}^4$, $\{\omega_\ell\}_{\ell=1}^4$ such that condition (ii) holds and inequality (i) is strictly verified. We identify below such $\{\lambda_\ell\}_{\ell=0}^4$ and $\{\omega_\ell\}_{\ell=1}^4$. The construction of the polar approximation then directly follows from Theorem 2.

We first set

$$ \lambda_0 = 0, \quad \lambda_j = \frac{1}{4}, \quad j = 1 \dots 4. $$

Because $\rho$ is assumed to be a positive-definite function, $\mathbf{1}_{2L}^\mathrm{T}\mathbf{G}^{-1}\mathbf{1}_{2L} > 0$ and condition (i) is strictly verified. We consider moreover the following definition for $\{\omega_\ell\}_{\ell=1}^4$:

$$ \omega_\ell = \omega \begin{pmatrix} \pm 1 \\ \pm 1 \end{pmatrix}, \quad \ell = 1 \dots 4, $$

for some $\omega \in \mathbb{R}$. Simple trigonometric operations show that this choice leads to the following “symmetric separable” low-rank kernel:

$$ \langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \cos(\omega(\theta(1) - \theta'(1))) \cos(\omega(\theta(2) - \theta'(2))). $$
With this definition, we finally have that $\forall i, j$:

$$ \langle \hat{a}(\theta_i), \hat{a}(\theta_j) \rangle = \rho(\theta_i(1) - \theta_j(1))\rho(\theta_i(2) - \theta_j(2)) $$

if and only if

$$ \omega = \frac{2}{\Delta}\arccos(\rho(\frac{\Delta}{2})). $$

We conclude this section by illustrating the approximation performance of this generalized polar approximation when $\rho$ is a Gaussian kernel:

$$ \rho(\tau) = \exp(-\frac{\tau^2}{2}). $$

This corresponds to the case where $a(\theta)$ is an isotropic Gaussian function with unit variance and mean equal to $\theta$; $H$ is then the set of square-integrable functions on $\Theta$.

In what follows, we compare the accuracy of the proposed polar approximation to the two-dimensional version of the Taylor approximation considered in [1]. In Fig. 1, we first compare the average square approximation error achieved by these two approaches (that is $\int \|a(\theta) - \hat{a}(\theta)\|^2 d\theta$) as a function of $\Delta$. It can be seen that the rate of decrease of the proposed polar decomposition ($\sim O(\Delta^4)$) is clearly superior to that of Taylor approximation ($\sim O(\Delta^2)$).

In a second experiment, we assess the ability of the two approximation to solve accurately the “atom selection” problem (3). We consider the particular setup where $r = a(\theta')$ so that the solution of the problem simply reads $\theta^* = \theta'$. We then evaluate $\hat{\theta}^*$ by solving (4) and compute the bias $b(\theta^*) = \hat{\theta}^* - \theta^*$. Due to isotropy, the two components of the bias are identical and, due to separability, component 1 (resp. 2) of the bias is invariant with respect to component 2 (resp. 1). So, in the present case, the bias is represented by a single curve, say $b_1(\theta(1), 0)$, the first component of the bias, as a function of the first location coordinate. This figure of merit is represented in Fig. 2. We see that the polar and Taylor approximations have quite different behaviors: while the Taylor approximation is exact at $\theta' = 0$, it linearly drifts away when $\theta'$ moves to the domain boundary. Conversely, the polar approximation is tight at $\theta' = (\pm\Delta/2, \pm\Delta/2)$, so the bias vanishes at the boundaries. Due to central symmetry in the dictionary kernel it also vanishes at the zero location and reaches a maximal bias at $\approx 0.3\Delta$. The latter maximal bias is approximately seventeen times lower than the maximal bias of the Taylor approximation.

Overall, these results confirm, for $d = 2$, the superior approximation accuracy of the polar approximation already demonstrated by [1] for $d = 1$.

## 4. CONCLUSIONS

In this paper, we address the problem of finding a “good” low-rank approximation of a parametric dictionary $\mathcal{A} =$

<figure><img src="image_3.png" /><figcaption>Fig. 1. Averaged MSE versus the approximation scale $\Delta$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Location estimation bias with respect to location.</figcaption></figure>

$\{a(\theta) : \theta \in \Theta\}$. In particular, we focus on dictionaries satisfying a translation-invariance property and search for low-rank approximations preserving this feature. We propose a new family of translation-invariant approximations, dubbed “generalized polar approximation”, interpolating a subset of atoms $\{a(\theta_j)\}_{j=1}^J$. The proposed family of approximations can be seen as a generalization of the so-called “polar approximation”, introduced by Ekanadham et al. in [1]. We illustrate our approach in a two-dimensional separable setup and emphasize that, similarly to Ekanadham’s results in the one-dimensional case, the proposed generalized polar decomposition outperforms Taylor approximation.
# 5. TECHNICAL DETAILS

## 5.1. Some technical Lemmas

We first make the following remark, showing the existence of family of translation-invariant vectors having a kernel taking the form of a sum of cosines:

**Lemma 2.** For any $\hat{\rho}$ of the form

$$ \hat{\rho}(\theta - \theta') = \lambda_0 + \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\omega_{\ell}^{\mathrm{T}}(\theta - \theta')) \quad \text{with } \lambda_{\ell} \ge 0, \qquad (19) $$

there exists a family of vectors $\hat{\mathcal{A}} = \{\hat{\mathbf{a}}(\theta) : \theta \in \Theta\}$ verifying

$$ \langle \hat{\mathbf{a}}(\theta), \hat{\mathbf{a}}(\theta') \rangle = \hat{\rho}(\theta - \theta') \quad \forall \theta, \theta' \in \Theta. \qquad (20) $$

Moreover, if

$$ \lambda_{\ell} > 0, \quad \omega_{\ell} \neq 0, \quad \omega_{\ell} \neq \omega_{\ell'} \quad \forall \ell \neq \ell' \quad \forall \ell, \ell' \ge 1 \qquad (21) $$

any family of vector $\hat{\mathcal{A}} = \{\hat{\mathbf{a}}(\theta) : \theta \in \Theta\}$ verifying (19) is such that

$$ \dim(\operatorname{span}(\hat{\mathcal{A}})) = 1_{\{\lambda_0 > 0\}} + 2L. \qquad (22) $$

*Proof:* Consider an orthonormal family of vectors of $\mathcal{H}$, say $\{\mathbf{w}_\ell\}_{\ell=0}^{2L}$ and define

$$ \hat{\mathbf{a}}(\theta) = \lambda_0^{\frac{1}{2}} \omega_0 + \sum_{\ell=1}^{L} \lambda_{\ell}^{\frac{1}{2}} (\cos(\omega_{\ell}^{\mathrm{T}} \theta) \mathbf{w}_{2\ell-1} + \sin(\omega_{\ell}^{\mathrm{T}} \theta) \mathbf{w}_{2\ell}). $$

This leads to

$$ \langle \hat{\mathbf{a}}(\theta), \hat{\mathbf{a}}(\theta') \rangle = \lambda_0 + \sum_{\ell=1}^{L} \lambda_{\ell} \left( \cos(\omega_{\ell}^{\mathrm{T}} \theta) \cos(\omega_{\ell}^{\mathrm{T}} \theta') + \sin(\omega_{\ell}^{\mathrm{T}} \theta) \sin(\omega_{\ell}^{\mathrm{T}} \theta') \right) $$

and equality (19) follows from a simple trigonometric identity.

The second statement can be shown as follows. Let $\hat{\mathcal{A}} = \{\hat{\mathbf{a}}(\theta) : \theta \in \Theta\}$ be a family of vector verifying (20) and let $\mathcal{K}$ be an operator defined as

$$ \mathcal{K}: L_2(\Theta) \to L_2(\Theta) \\ f(\theta') \mapsto \int \langle \hat{\mathbf{a}}(\theta), \hat{\mathbf{a}}(\theta') \rangle f(\theta') d\theta'. \qquad (23) $$

We have that

$$ \dim(\operatorname{span}(\hat{\mathcal{A}})) = \operatorname{rank}(\mathcal{K}). \qquad (24) $$

Now, from (19)-(20), we have that

$$ \mathcal{K} f(\theta) = \lambda_0 \int f(\theta') d\theta' + \sum_{\ell=1}^{L} \lambda_{\ell} \left( \cos(\omega_{\ell}^{\mathrm{T}} \theta) \int \cos(\omega_{\ell}^{\mathrm{T}} \theta') f(\theta') d\theta' + \sin(\omega_{\ell}^{\mathrm{T}} \theta) \int \sin(\omega_{\ell}^{\mathrm{T}} \theta') f(\theta') d\theta' \right). $$

Since $\{1\} \cup \{\sin(\omega_{\ell}^{\mathrm{T}} \theta)\}_{\ell=1}^{L} \cup \{\cos(\omega_{\ell}^{\mathrm{T}} \theta)\}_{\ell=1}^{L}$ form a family of linearly independent functions in $L_2(\Theta)$ under hypothesis (21), $\operatorname{rank}(\mathcal{K}) = 1_{\{\lambda_0 > 0\}} + 2L$ and the result follows from (24). □

The next lemma below introduces a remarkable identity which must be verified by kernels of the form (19).

**Lemma 3.** Let $\hat{\rho}(\theta - \theta')$ be defined in (19) with $\lambda_0 = 0$ and assume (21) holds. Then,

(i) there exists $\{\theta_j\}_{j=1}^{2L}$ such that the following matrix is invertible:

$$ \mathbf{G} = [\hat{\rho}(\theta_i - \theta_j)]_{i,j \in \mathbb{R}^{2L \times 2L}} \qquad (25) $$

(ii) for any $\{\theta_j\}_{j=1}^{2L}$ such that $\mathbf{G}$ is invertible, the following relation holds:

$$ \hat{\rho}(\theta - \theta') = \sum_{i=1}^{2L} \sum_{j=1}^{2L} \mathbf{H}(i, j) c_i(\theta) c_j(\theta') \qquad (26) $$

where $c_j(\theta) \triangleq \hat{\rho}(\theta - \theta_j)$ and $\mathbf{H} = \mathbf{G}^{-1}$.

*Proof:* From Lemma 2, there exists a family of atoms $\hat{\mathcal{A}} = \{\hat{\mathbf{a}}(\theta) : \theta \in \Theta\}$ verifying $\langle \hat{\mathbf{a}}(\theta), \hat{\mathbf{a}}(\theta') \rangle = \hat{\rho}(\theta - \theta')$ and such that $\dim(\operatorname{span}(\hat{\mathcal{A}})) = 2L$. Hence, there exists $\{\theta_j\}_{j=1}^{2L}$ such that $\{\hat{\mathbf{a}}(\theta_j)\}_{j=1}^{2L}$ are linearly independent. Statement (i) then simply follows from the fact that the Gram matrix of any set of linearly independent vectors is invertible.

Statement (ii) can be shown as follows. Since $\{\hat{\mathbf{a}}(\theta_j)\}_{j=1}^{2L}$ are linearly independent and, from Lemma 2, $\dim(\operatorname{span}(\hat{\mathcal{A}})) = 2L$, these vectors form a basis of $\operatorname{span}(\hat{\mathcal{A}})$. Therefore, any $\hat{\mathbf{a}}(\theta) \in \hat{\mathcal{A}}$ can be expressed as a function of $\{\hat{\mathbf{a}}(\theta_j)\}_{j=1}^{2L}$. This leads to

$$ \hat{\mathbf{a}}(\theta) = \sum_{j=1}^{2L} \hat{\mathbf{a}}(\theta_j) \alpha_j \qquad (27) $$

where

$$ \alpha_j = \sum_{i=1}^{2L} \mathbf{H}(j, i) \langle \hat{\mathbf{a}}(\theta_i), \hat{\mathbf{a}}(\theta) \rangle = \sum_{i=1}^{2L} \mathbf{H}(j, i) c_i(\theta). \qquad (28) $$
Using (27)-(28), we have

$$ \langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \sum_{i=1}^{2L} \sum_{j=1}^{2L} \mathbf{H}(i, j) c_i(\theta) c_j(\theta'). \quad (29) $$

We finally obtain (26) by noticing that $\langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \hat{\rho}(\theta - \theta')$ by definition. $\square$

The next lemma makes the connection between condition (i) of Theorem 1 and the existence of an affine plane containing a set $\{a(\theta_j)\}_{j=1}^{2L}$ and whose minimum-norm vector has a magnitude equal to $\sqrt{\lambda_0}$:

**Lemma 4.** The following conditions are equivalent:

(i) $\exists v_0 \in \mathcal{H}$ such that

$$ \|v_0\|^2 = \lambda_0 \quad (30) $$

$$ \langle v_0, a(\theta_j) - v_0 \rangle = 0 \quad \forall j = 1 \dots 2L, \quad (31) $$

(ii) $\lambda_0 \le (\mathbf{1}_{2L} \mathbf{G}^{-1} \mathbf{1}_{2L})^{-1}$

Moreover, the family $\{a(\theta_j) - v_0\}_{j=1}^{2L}$ is free if and only if the inequality in (ii) holds strictly.

*Proof:* Condition (31) is equivalent to

$$ \langle v_0, a(\theta_j) \rangle = \|v_0\|^2 \quad \forall j = 1 \dots 2L. \quad (32) $$

The existence of some $v_0 \in \mathcal{H}$ verifying (30)-(31) can then also be reformulated as

$$ \exists v_0 \in \mathcal{H} \text{ s.t. } \left\{ \begin{array}{l} \|v_0\|^2 = \lambda_0, \\ \langle v_0, a(\theta_j) \rangle = \lambda_0 \quad \forall j = 1 \dots 2L. \end{array} \right. \quad (33) $$

Since the vectors $\{a(\theta_j)\}_{j=1}^{2L}$ are assumed to be linearly independent, the linear system in (33) has an infinity of solutions of the form

$$ v_0 = \lambda_0 \sum_{j=1}^{2L} a(\theta_j) \alpha_j + v \quad (34) $$

with

$$ \alpha_j = \sum_{i=1}^{2L} \mathbf{G}^{-1}(j, i) \langle v, a(\theta_j) \rangle = 0 \quad \forall j = 1 \dots 2L. \quad (35) $$

Taking the square norm of both sides of (34) and taking (35) into account leads to

$$ \|v_0\|^2 = \lambda_0^2 \sum_{i=1}^{2L} \sum_{j=1}^{2L} \mathbf{G}^{-1}(i, j) + \|v\|^2. \quad (36) $$

Hence a solution to the two constraints in (33) exists if and only if (ii) holds.

Finally, the last assertion is a consequence of the definiton of $v_0$ in (34)-(35). $\square$

**Lemma 5.** Let $\hat{\rho}(\theta - \theta')$ be defined in (19) with $\lambda_0 > 0$ and assume (21) holds. Then,

(i) there exists $\{\theta_j\}_{j=1}^{2L+1}$ such that the following matrix is invertible:

$$ \mathbf{G} = [\hat{\rho}(\theta_i - \theta_j)]_{i,j \in \mathbb{R}^{2L+1} \times 2L+1} \quad (37) $$

(ii) for any $\{\theta_j\}_{j=1}^{2L+1}$ such that $\mathbf{G}$ is invertible, the following relations holds, $\forall \ell$:

$$ \begin{aligned} & \sum_{i,j=1}^{2L+1} \mathbf{G}^{-1}(j, i) = \frac{1}{\lambda_0} \\ & \sum_{i,j=1}^{2L+1} \mathbf{G}^{-1}(j, i) \cos(\omega_{\ell}^{\mathrm{T}} \theta_j) = 0 \\ & \sum_{i,j=1}^{2L+1} \mathbf{G}^{-1}(j, i) \sin(\omega_{\ell}^{\mathrm{T}} \theta_j) = 0 \end{aligned} \quad (38) $$

*Proof:* From Lemma 2, there exists a family of atoms $\hat{\mathcal{A}} = \{\hat{a}(\theta) : \theta \in \Theta\}$ verifying $\langle \hat{a}(\theta), \hat{a}(\theta') \rangle = \hat{\rho}(\theta - \theta')$ and such that $\dim(\mathrm{span}(\hat{\mathcal{A}})) = 2L + 1$. Hence, there exists $\{\theta_j\}_{j=1}^{2L+1}$ such that $\{\hat{a}(\theta_j)\}_{j=1}^{2L+1}$ are linearly independent. Statement (i) then simply follows from the fact that the Gram matrix of any set of linearly independent vectors is invertible.

Statement (ii) can be shown as follows. $\mathbf{G}$ can be factored as

$$ \mathbf{G} = \mathbf{U}\mathbf{D}\mathbf{U}^T, \quad (39) $$

with

$$ \begin{aligned} \mathbf{D} &= \mathrm{diag}(\lambda_0, \frac{\lambda_1}{2}, \frac{\lambda_1}{2}, \dots, \frac{\lambda_L}{2}, \frac{\lambda_L}{2}), \\ \mathbf{U} &= [u(\mathbf{0}), u(\omega_1), u(-\omega_1), \dots, u(\omega_L), u(-\omega_L)], \\ u(\omega) &= [\exp(i\omega^{\mathrm{T}}\theta_1), \dots, \exp(i\omega^{\mathrm{T}}\theta_{2L+1})]^{\mathrm{T}}. \end{aligned} $$

Hence, taking the inverse of both sides of (39), we have the following matrix equality: $\mathbf{U}^{\mathrm{T}}\mathbf{G}^{-1}\mathbf{U} = \mathbf{D}^{-1}$. The expressions stated in (38) are then simply an explicit rewriting of the equalities corresponding to the first row (or column) of $\mathbf{D}^{-1}$. $\square$

<figure><img src="image_5.png" /></figure>

## 5.2. Proof of Lemma 1

*Proof:* First consider the case $\lambda_0 = 0$, from Lemma 2, $\dim(\mathrm{span}(\hat{\mathcal{A}})) = 2L$, $\hat{\mathcal{A}}$ is a 2L-dimensional vector space or equivalently a 2L-dimensional affine space with zero as minimum-norm vector.

Consider now the case $\lambda_0 > 0$. From Lemma 2, $\dim(\mathrm{span}(\hat{\mathcal{A}})) = 2L + 1$. Hence there exists $\{\theta_j\}_{j=1}^{2L+1}$ such that $\{\hat{a}(\theta_j)\}_{j=1}^{2L+1}$ are linearly independent. $\{\hat{a}(\theta_j)\}_{j=1}^{2L+1}$ defines a 2L-dimensional affine space. Let $v_0$ be the minimum-norm vector of this
affine space. Then, there exists $2L + 1$ scalars $\{\alpha_j\}_{j=1}^{2L+1}$ summing to one such that

$$v_0 = \sum_{j=1}^{2L+1} \hat{a}(\theta_j) \alpha_j. \quad (40)$$

Simple algebraic considerations show moreover that

$$\alpha_j = \frac{\sum_{i=1}^{2L+1} \mathbf{G}^{-1}(j, i)}{\sum_{i,j=1}^{2L+1} \mathbf{G}^{-1}(j, i)}, \quad (41)$$

where $\mathbf{G}^{-1}(j, i)$ is the Gram matrix of the atoms $\{\hat{a}(\theta_j)\}_{j=1}^{2L+1}$. Then $\|v_0\|^2$ can be expanded as follows

$$\begin{aligned} \|v_0\|^2 = & \lambda_0 \left( \sum_{j=1}^{2L+1} \alpha_j \right)^2 \\ & + \sum_{\ell=1}^{L} \lambda_{\ell} \left( \sum_{j=1}^{2L+1} \alpha_j \cos(\omega_{\ell}^{\mathrm{T}} \theta_j) \right)^2 \\ & + \sum_{\ell=1}^{L} \lambda_{\ell} \left( \sum_{j=1}^{2L+1} \alpha_j \sin(\omega_{\ell}^{\mathrm{T}} \theta_j) \right)^2. \end{aligned} \quad (42)$$

Using Lemma 5 and since the scalars $\{\alpha_j\}_{j=1}^{2L+1}$ sum to one, it follows that

$$\|v_0\|^2 = \lambda_0. \quad (43)$$

It remains to show that the affine space defined by $\{\hat{a}(\theta_j)\}_{j=1}^{2L+1}$ contains all the elements of $\hat{\mathcal{A}}$. For any $\delta\theta \in \Theta$, let $v_0(\delta\theta)$ be the minimum norm vector of the affine space defined by $\{\hat{a}(\theta_j + \delta\theta)\}_{j=1}^{2L+1}$. By translation invariance, $\|v_0(\delta\theta)\| = \|v_0\|$ and

$$v_0(\delta\theta) = \sum_{j=1}^{2L+1} \hat{a}(\theta_j + \delta\theta) \alpha_j. \quad (44)$$

We show hereafter that $v_0(\delta\theta) = v_0$. This is equivalent to $\langle v_0(\delta\theta), v_0 \rangle = \|v_0\|^2 = \lambda_0$. $\langle v_0(\delta\theta), v_0 \rangle$ expands as follows:

lows:

$$\begin{aligned} \langle v_0(\delta\theta), v_0 \rangle &= \lambda_0 \sum_{i,j=1}^{2L+1} \alpha_i \alpha_j \\ & \quad + \sum_{\ell=1}^{L} \lambda_{\ell} \sum_{i,j=1}^{2L+1} \alpha_i \alpha_j \cos(\omega_{\ell}^{\mathrm{T}}(\theta_i - \theta_j - \delta\theta)) \\ &= \lambda_0 \\ & \quad + \sum_{\ell=1}^{L} \lambda_{\ell} \cos \omega_{\ell}^{\mathrm{T}} \delta\theta \sum_{i,j=1}^{2L+1} \alpha_i \alpha_j \cos(\omega_{\ell}^{\mathrm{T}}(\theta_i - \theta_j)) \\ & \quad + \sum_{\ell=1}^{L} \lambda_{\ell} \sin \omega_{\ell}^{\mathrm{T}} \delta\theta \sum_{i,j=1}^{2L+1} \alpha_i \alpha_j \sin(\omega_{\ell}^{\mathrm{T}}(\theta_i - \theta_j)) \\ &= \lambda_0 \\ & \quad + \sum_{\ell=1}^{L} \lambda_{\ell} \cos \omega_{\ell}^{\mathrm{T}} \delta\theta \left( \sum_{i}^{2L+1} \alpha_i \cos(\omega_{\ell}^{\mathrm{T}} \theta_i) \right)^2 \\ & \quad + \sum_{\ell=1}^{L} \lambda_{\ell} \cos \omega_{\ell}^{\mathrm{T}} \delta\theta \left( \sum_{i}^{2L+1} \alpha_i \sin(\omega_{\ell}^{\mathrm{T}} \theta_i) \right)^2. \end{aligned}$$

By Lemma 5, all the factors for $\ell \ge 1$ vanish, so $\langle v_0(\delta\theta), v_0 \rangle = \lambda_0 = \|v_0\|^2$. It follows that

$$\langle \hat{a}(\theta_j + \delta\theta) - v_0, v_0 \rangle = 0, \forall j, \forall \delta\theta. \quad (45)$$

This is equivalent to

$$\langle \hat{a}(\theta) - v_0, v_0 \rangle = 0, \forall \theta. \quad (46)$$

Now define dictionary $\hat{b}(\theta) = \hat{a}(\theta) - v_0$, using (46)

$$\begin{aligned} \langle \hat{b}(\theta), \hat{b}(\theta') \rangle &= \langle \hat{a}(\theta), \hat{a}(\theta') \rangle - \|v_0\|^2 \\ &= \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\omega_{\ell}^{\mathrm{T}}(\theta - \theta')). \end{aligned}$$

Finally, the dictionary $\hat{b}(\theta)$ fulfills (10) with $\lambda_0 = 0$, so from the first part of the proof, $\hat{b}(\theta) = \hat{a}(\theta) - v_0$ spans a 2L-dimensional vector space. Therefore $\hat{a}(\theta)$ spans a 2L-dimensional affine space with minimum-norm vector $v_0$ such that $\|v_0\|^2 = \lambda_0$. $\square$

### 5.3. Proof of Theorem 2

*Proof:* We first note that matrix $\mathbf{H}_0$ is well-defined since from (14), the family $\{a(\theta_j) - v_0\}_{j=1}^J$ is free and its Gram matrix is therefore invertible.

Next, using (13) we have

$$\langle a(\theta_i), a(\theta_j) \rangle = \|v_0\|^2 + \langle a(\theta_j) - v_0, a(\theta_i) - v_0 \rangle.$$
We then obtain from (12) and Theorem 1(ii):

$$ \begin{aligned} \langle \mathbf{a}(\boldsymbol{\theta}_i) - \mathbf{v}_0, \mathbf{a}(\boldsymbol{\theta}_j) - \mathbf{v}_0 \rangle &= \sum_{\ell=1}^{L} \lambda_{\ell} \cos(\boldsymbol{\omega}_{\ell}^{\mathrm{T}}(\boldsymbol{\theta}_i - \boldsymbol{\theta}_j)) \\ &= c_j(\boldsymbol{\theta}_i). \end{aligned} $$

Hence, by definition of $\mathbf{H}_0$, we have

$$ \sum_{k=1}^{L} \mathbf{H}_0(k, j) c_k(\boldsymbol{\theta}_i) = \delta_{i-j} \quad (47) $$

Combining (15) and (17), with this identity leads to

$$ \begin{aligned} \hat{\mathbf{a}}(\boldsymbol{\theta}_i) &= \mathbf{v}_0 + \sum_{k=1}^{2L} \mathbf{v}_k c_k(\boldsymbol{\theta}_i) \\ &= \mathbf{v}_0 + \sum_{k=1}^{2L} \sum_{j=1}^{2L} (\mathbf{a}(\boldsymbol{\theta}_j) - \mathbf{v}_0) \mathbf{H}(k, j) c_k(\boldsymbol{\theta}_i) \\ &= \mathbf{v}_0 + \sum_{j=1}^{2L} (\mathbf{a}(\boldsymbol{\theta}_j) - \mathbf{v}_0) \sum_{k=1}^{2L} \mathbf{H}(k, j) c_k(\boldsymbol{\theta}_i) \\ &= \mathbf{v}_0 + \sum_{j=1}^{2L} (\mathbf{a}(\boldsymbol{\theta}_j) - \mathbf{v}_0) \delta_{i-j} \\ &= \mathbf{a}(\boldsymbol{\theta}_i). \end{aligned} \quad (48) $$

This shows that (9) is verified.

Moreover, using (15)-(18) we have that

$$ \langle \hat{\mathbf{a}}(\boldsymbol{\theta}), \hat{\mathbf{a}}(\boldsymbol{\theta}') \rangle = \lambda_0 + \sum_{i=1}^{2L} \sum_{j=1}^{2L} \mathbf{H}(i, j) c_i(\boldsymbol{\theta}) c_j(\boldsymbol{\theta}'). $$

(10) then directly follows from Lemma 3.

<figure><img src="image_6.png" /></figure>

## 5.4. Proof of Theorem 1

*Proof:* We first show that the existence of a family of atoms (2) verifying (9)-(10) for $J = K = 2L$, implies conditions (i) and (ii). Condition (ii) is a direct consequence of (9)-(10). Condition (i) can be shown as follows. We first note from Lemma 1 that any family $\hat{\mathcal{A}} = \{\hat{\mathbf{a}}(\boldsymbol{\theta}) : \boldsymbol{\theta} \in \Theta\}$ verifying (10) span a $2L$-dimensional affine subspace with minimum-norm vector $\mathbf{v}_0$ obeying

$$ \|\mathbf{v}_0\|^2 = \lambda_0. \quad (49) $$

Moreover, since $\{\mathbf{a}(\boldsymbol{\theta}_j)\}_{j=1}^{2L} \subset \hat{\mathcal{A}}$ from (9), we have

$$ \langle \mathbf{v}_0, \mathbf{a}(\boldsymbol{\theta}_j) - \mathbf{v}_0 \rangle = 0 \quad \forall j = 1 \dots 2L. \quad (50) $$

Now (49)-(50) is equivalent to (i) by virtue of Lemma 4.

The sufficiency of (ii) and $\lambda_0 < (\mathbf{1}_{2L}^{\mathrm{T}}\mathbf{G}^{-1}\mathbf{1}_{2L})^{-1}$ for the existence of a family of atoms (2) verifying (9)-(10) is a direct consequence of Theorem 2.

<figure><img src="image_7.png" /></figure>

# 6. REFERENCES

[1] Chaitanya Ekanadham, Daniel Tranchina, and Eero P. Simoncelli, “Recovery of sparse translation-invariant signals with continuous basis pursuit,” *Signal Processing, IEEE Transactions on*, vol. 59, no. 10, pp. 4735–4744, Oct. 2011.

[2] Kristian Bredies and Hanna Katriina Pikkarainen, “Inverse problems in spaces of measures,” *ESAIM: Control, Optimisation and Calculus of Variations*, vol. 19, no. 1, pp. 190–218, 2013.

[3] Karin C. Knudson, Jacob L. Yates, Alexander C. Huk, and Jonathan W. Pillow, “Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit,” in *Advances in Neural Information Processing*, 2014.

[4] F. Champagnat and C. Herzet, “Atom selection in continuous dictionaries: Reconciling polar and svd approximations,” in *ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, 2019, pp. 5516–5520.

[5] Nikhil Rao, Parikshit Shah, and Stephen Wright, “Forward–backward greedy algorithms for atomic norm regularization,” *IEEE Transactions on Signal Processing*, vol. 63, no. 21, pp. 5798–5811, 2015.

[6] Clément Elvira, Rémi Gribonval, Charles Soussen, and Cédric Herzet, “OMP and continuous dictionaries: is k-step recovery possible?,” in *ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, Brighton, United Kingdom, May 2019, IEEE, pp. 5546–5550, IEEE.