---
abstract: 'In this paper we develop constructive invertibility conditions for the twisted convolution. Our approach is based on splitting the twisted convolution with rational parameters into a finite number of weighted convolutions, which can be interpreted as another twisted convolution on a finite cyclic group. In analogy with the twisted convolution of finite discrete signals, we derive an anti-homomorphism between the sequence space and a suitable matrix algebra which preserves the algebraic structure. In this way, the problem reduces to the analysis of finite matrices whose entries are sequences supported on corresponding cosets. The invertibility condition then follows from Cramer’s rule and Wiener’s lemma for this special class of matrices. The problem results from a well known approach of studying the invertibility properties of the Gabor frame operator in the rational case. The presented approach gives further insights into Gabor frames. In particular, it can be applied for both the continuous (on ${{\mathbb{R}}^d}$) and the finite discrete setting. In the latter case, we obtain algorithmic schemes for directly computing the inverse of Gabor frame-type matrices equivalent to those known in the literature.'
author:
- 'Yonina C. Eldar[^1], Ewa Matusiak[^2], Tobias Werther $^\dagger$'
bibliography:
- 'twc.bib'
title: A Constructive Inversion Framework for Twisted Convolution
---

\[section\] \[theorem\][Definition]{} \[theorem\][Lemma]{} \[theorem\][Proposition]{} \[theorem\][Corollary]{} \[theorem\][Example]{} \[theorem\][Remark]{}

[Subject Classification: 44A35, 15A30, 42C15]{}

[Key Words: Twisted convolution, Wiener’s Lemma, Gabor frame, Invertibility of operators]{}

Introduction
============

Twisted convolution arises naturally in the context of time frequency operators, more specifically in the treatment of Gabor frames [@CH03; @Gro01]. The study of inversion schemes of twisted convolution has, therefore, a major impact on the analysis of Gabor frames. Our method is originated by the Janssen representation of Gabor frame operators [@Jan95] and simplifies the approach given in [@WEN05]. A different, however, equivalent method for studying Gabor frame operators is the well known Zibulski-Zeevi representation [@ZZ97] based on a generalized Zak-transform.

In contrast to the standard convolution, the twisted convolution is not commutative. This is opposed to the possibility of applying powerful tools from harmonic analysis, such as Wiener’s Lemma, in order to study twisted convolution operators. Recently, in [@WEN05], the authors described an new approach to classify the invertibility of $\ell^1$-sequences with respect to the twisted convolution for rational parameters.

In this manuscript we extend the idea of [@WEN05] in the sense that we take a different approach which allows far better insights into the problem. Specifically, we only deal with sequences and show explicitly how efficient inversion schemes can be derived by rather simple (though sophisticated) manipulations of the twisted convolution. The essential idea is to split up the twisted convolution into a finite number of sums that can be incorporated into a special matrix algebra. In this matrix algebra we then prove a special type of Wiener Lemma which is the most challenging part from a mathematical perspective.

The paper is organized as follows. The first section briefly outlines the basic definition of the twisted convolution. In this section we further discuss the example of twisted convolution on the finite group $Z_p\times Z_p$. This example serves the purpose to motivate the introduction of the matrix algebra that appears in Section 3 where we prove Wiener’s Lemma for a special subalgebra. Section 4 links the twisted convolution to time-frequency operators. More specifically, it shows how the results shown in Section 3 can be used in the context of Gabor frames. In the last section, we give a short outline of the application of the presented approach for inverting frame-like Gabor operators.

Twisted Convolution
===================

Let $p$ and $q$ be integers and relatively prime. We define the [*twisted convolution*]{} for sequences $a,b\in\ell^1({\mathbb{Z}^{2d}})$ by $$\label{eq:twconv}
({{a}\,{\natural}\,{b}})_{m,n} = \sum_{k,l\in{\mathbb{Z}^d}} a_{k,l}b_{m-k,n-l}{\omega}^{{ (m-k) \, \cdot \, l}}$$ where ${\omega}= e^{2\pi i q/p}$ and $\cdot$ denotes the inner product in ${{\mathbb{R}}^d}$. Although the twisted convolution depends on $p,q$ we do not specify this dependence because $p,q$ will always be given and fixed beforehand. In Section 4 we show how the twisted convolution is related to a class of operators with a special time-frequency representation.

In contrast to the conventional convolution with symbol $\ast$, in which ${\omega}=1$, the twisted convolution is not commutative, and turns $\ell^1({\mathbb{Z}^{2d}})$ into a non-commutative algebra with the delta-sequence $\delta$ as its unit element.

We tackle the problem to study the invertibility of twisted convolution operators. Non-commutativity is the main subtle point in this problem. In fact, the question when the mapping $$C_b:a\in\ell^1 \rightarrow {{a}\,{\natural}\,{b}} \in \ell^1$$ for some $b\in\ell^1$ is invertible and how we can compute the inverse is more difficult than for a commutative setting. In particular, Wiener’s Lemma which deals with the problem that if, for some $b \in \ell^1$, $C_b$ is invertible on $\ell^2$ then the inverse is generated from an element again in $\ell^1$, has to be proven separately. An abstract and more general proof of Wiener’s Lemma for twisted convolution is given in [@GL03]. Herein, we focus on a constructive method for studying the invertibility of the twisted convolution with the rational parameter $q/p$.

In the following subsections we study the twisted convolution in a finite setting and draw analogies for approaching the problem of invertibility of $C_b$ in the general case.

Twisted convolution on $\bf {Z_p}\times {Z_p}$
----------------------------------------------

In what follows we describe the twisted convolution on the finite group $F = {Z_p}\times {Z_p}$. The standard (commutative) convolution of two elements $f,g\in{\mathbb{C}}^{p\times p}$ is defined by $$({{f}\,\ast\,{g}})_{m,n} =\sum_{k,l=0}^{p-1} f_{k,l}g_{m-k,n-l}\,,$$ where operations on indices is performed modulo $p$.

In analogy to the infinite case, we define the twisted convolution ${{f}\,{\natural}\,{g}}$ of two elements $f,g\in{\mathbb{C}}^{p\times p}$ by $$({{f}\,{\natural}\,{g}})_{m,n} = \sum_{k,l = 0}^{p-1}  f_{k,l} g_{m-k,n-l}
   {\omega}^{(m-k)l}$$ with ${\omega}= e^{2\pi i q/p}$. For a fixed $g$, the twisted convolution can be seen as a linear mapping $C_g:f \rightarrow {{f}\,{\natural}\,{g}}$ whose matrix $G$ is block circulant with $p$ blocks, i.e., $$G = C(G_0,G_{p-1},\dots,G_1)
   =\left (
   \begin{array}{cccc} G_0 & G_{p-1} & \cdots & G_1 \\
                            G_1 & G_0 & \cdots & G_2 \\
                \vdots & \vdots & & \vdots \\
                G_{p-1} & G_{p-2} & \cdots & G_0
   \end{array} \right )\,.$$ Each block has entries of the form $$(G_j)_{kl} = {\omega}^{jl}g_{j,k-l}\,.$$ Note that for the regular convolution each block is itself circulant. For the invertibility of block circulant matrices we apply a well known result from Fourier analysis.

[[@Dav94]]{} The matrix $G=C(G_0,G_{p-1},\dots,G_1)$ is invertible if and only if every $\hat{G}_s = \sum_{r=0}^{p-1}e^{-2\pi i sr/p}G_r$, $s=0,\dots,p-1$, is invertible. In this case $$G^{-1} = C(H_0,H_{p-1},\dots,H_1)$$ where $H_r = \frac{1}{p}\sum_{s=0}^{p-1}e^{2\pi i sr/p}(\hat{G}_s)^{-1}\,.$

By analyzing $\hat{G}_s$, we see that all blocks are unitary equivalent, in the sense that $$T_r\hat{G}_sT^*_r = \hat{G}_{s-qr}\,,$$ where $T_r$ denotes the unitary matrix with entries $$(T_r)_{kl} =
   \left\{
   \begin{array}{cl}
     1 & \mbox{if} \quad p-r = l-k, \\
     0 & \mbox{else}\,.
   \end{array}
   \right.$$ Since $p$ and $q$ are relatively prime, we obtain all blocks by such a unitary transformation. This implies that showing that if $\hat{G}_0$ is invertible, then all $\hat{G}_s$ are invertible for $s=1,\dots,p-1$. In other words, the $p\times p$ matrix $\hat{G}_0$ contains all the information about the invertibility of $C_g$. An easy computation shows that the entries of $\hat{G}_0$ are given by $$\label{eq:entries}
   (\hat{G}_0)_{n,l} = \sum_{k=0}^{p-1}{\omega}^{nl}g_{k,n-l}\,.$$ We will later see that this observation motivates the matrix algebra that we introduce to study the invertibility of the twisted convolution.

Now, also all $\hat{G}^{-1}_s$ satisfy the same unitary equivalence. It follows that we can read from $\hat{G}^{-1}_0$ the element $g^{-1}$ which inverts the twisted convolution $f\rightarrow
{{f}\,{\natural}\,{g}}$, i.e., ${{g^{-1}}\,{\natural}\,{g}} = {{g}\,{\natural}\,{g^{-1}}} = \delta.$

The twisted convolution on $Z_p\times Z_p$ serves as analogy for modelling the twisted convolution for the continuous and the finite dimensional case.

Main results
============

Our aim is to find a way to describe those sequences that have an inverse in $(\ell^1({\mathbb{Z}^{2d}}),{\natural})$. To this end we divide the twisted convolution into a finite sum of weighted normal convolutions of sequences that have disjoint support. We define such a sequence $a^{r,s}$ by $$\label{eq:coset-seq}
   (a^{r,s})_{k,l} = \left\{
   \begin{array}{ll}
      a_{k,l} \quad & \mbox{if} \quad (k,l) \equiv_p (r,s)\,, \\ [.2cm]
      0 & \mbox{else,}
   \end{array}
   \right.$$ where $r,s \in {{Z_p}^d}$. Obviously, $a^{r,s}$ is supported on the coset $(r + p{\mathbb{Z}^d}) \times (s + p{\mathbb{Z}^d})$ and $a = \sum_{r,s \in {{Z_p}^d}}
a^{r,s}$. For a sequence $a$ having a coset support only for one index, e.g., on ${\mathbb{Z}^d}\times (s+p{\mathbb{Z}^d})$, we simply write $a^{\cdot,s}$. We write $\equiv_p$ for denoting the equivalence of integers modulo $p$. The idea of slitting a sequence into a sum of sequences supported on cosets has first been introduced by K. Gr[ö]{}chenig and W. Kozek in [@GK97].

\[lem1\] Let $a,b,c$ be in $\ell^1({\mathbb{Z}^{2d}})$.

-   For $r,s,u,v \in {{Z_p}^d}$, ${{a^{r,s}}\,\ast\,{b^{u,v}}}$ is a sequence supported on the coset $(u+r+p{\mathbb{Z}^d}) \times (v+s+p{\mathbb{Z}^d})$.

-   If $c=c^{\cdot,0}$ is invertible in $(\ell^1,\ast)$, then $c^{-1}$ is also supported on ${\mathbb{Z}^d}\times p{\mathbb{Z}^d}$.

Let $a^{r,s}, b^{u,v}$ be sequences in $\ell^1({\mathbb{Z}^{2d}})$ and $k,l \in {{Z_p}^d}$. Then $$\begin{aligned}
   (a^{r,s} \ast b^{u,v})_{k+p{\mathbb{Z}^d},l+p{\mathbb{Z}^d}} &=& \sum_{m,n \in {\mathbb{Z}^d}} (a^{r,s})_{m,n}
   (b^{u,v})_{k+p{\mathbb{Z}^d}-m,l+p{\mathbb{Z}^d}-n} \\
   &=& \sum_{m,n \in {{Z_p}^d}} \sum_{(t,w) \equiv_p (m,n)} (a^{r,s})_{t,w}
   (b^{u,v})_{k+p{\mathbb{Z}^d}-t,l+p{\mathbb{Z}^d}-w}.\end{aligned}$$ Since $a^{r,s}$ is nonzero only for $(t,w) \equiv_p (r,s)$, and $b^{u,v}$ for $(k-t,l-w) \equiv_p (u,v)$, we obtain that $(k,l)$ has to be equivalent to $(u+r,v+s)$ modulo $p$ for $a^{r,s} \ast b^{u,v}$ to be nonzero.

To show (b), let $c=c^{\cdot,0}$ be invertible and $e$ be its inverse. Then $$\delta = c \ast e = c^{\cdot,0} \ast \big( \sum_{s \in {{Z_p}^d}} e^{\cdot,s} \big )
   = \sum_{s \in {{Z_p}^d}} c^{\cdot,0} \ast e^{\cdot,s},$$ where, by previous calculations, $c^{\cdot,0} \ast e^{\cdot,s}$ is a sequence supported on ${\mathbb{Z}^d}\times (s+p{\mathbb{Z}^d})$ for each $s \in {{Z_p}^d}$. Since $\delta =
\sum_{s \in {{Z_p}^d}} \delta^{\cdot,s}$, and elements of the sum have disjoint supports, $c^{\cdot,0} \ast e^{\cdot,s} = \delta^{\cdot,s}$. But since $\delta^{\cdot,s} = 0$ for $s \neq 0$ and $\delta^{\cdot,0} =
\delta$, we conclude that $$c^{\cdot,0} \ast e^{\cdot,s} = \left \{
   \begin{array}{cc}
      \delta & s = 0\\ [.2cm]
      0 & s \neq 0
   \end{array} \right.$$ and therefore $e = e^{\cdot,0}$.

With Definition (\[eq:coset-seq\]), we obtain for $u,v \in {{Z_p}^d}$ $$\begin{aligned}
   ({{a}\,{\natural}\,{b}})_{u+p{\mathbb{Z}^d},v+p{\mathbb{Z}^d}} & = &
   \sum_{k,l \in {\mathbb{Z}^d}}a_{k,l}b_{u+p{\mathbb{Z}^d}-k,v+p{\mathbb{Z}^d}-l} {\omega}^{{ (u-k) \, \cdot \, l}} \\
   & = & \sum_{r,s \in {{Z_p}^d}} \sum_{(k,l)\equiv_p (r,s)} a_{k,l}
   b_{u+p{\mathbb{Z}^d}-k,v+p{\mathbb{Z}^d}-l} {\omega}^{{ (u-r) \, \cdot \, s}} \\
   & = & \sum_{r,s \in {{Z_p}^d}} \sum_{k,l \in {\mathbb{Z}^d}}
   (a^{r,s})_{k,l}(b^{u-r,v-s})_{u+p{\mathbb{Z}^d}-k,v+p{\mathbb{Z}^d}-l} {\omega}^{{ (u-r) \, \cdot \, s}} \\
   & = & \sum_{r,s \in {{Z_p}^d}} (a^{r,s}\ast
   b^{u-r,v-s})_{u+p{\mathbb{Z}^d},v+p{\mathbb{Z}^d}} {\omega}^{{ (u-r) \, \cdot \, s}}\,.\end{aligned}$$ In a more compact notation we have $$\label{eq:comp}
   ({{a}\,{\natural}\,{b}})^{u,v} = \sum_{r,s \in {{Z_p}^d}} a^{r,s} \ast b^{u-r,v-s}
   {\omega}^{{ (u-r) \, \cdot \, s}}\,.$$ We observe now that the upper indices in (\[eq:comp\]) behave like a twisted convolution in ${{Z_p}^d}\times {{Z_p}^d}$. What changes is that we have sequences as elements and standard convolution instead of multiplication.

Motivated by the block circulant structure of the twisted convolution on ${Z_p}\times{Z_p}$ as described in the previous section, we introduce a new matrix algebra which is isomorphic to $(\ell^1({\mathbb{Z}^{2d}}),{\natural})$.

Before we do so, we fix an ordering of the elements from ${{Z_p}^d}$. Let $N= p^d$ and ${\mathcal{I}}=\{1,\ldots,N \}$. Then, to each $i \in {\mathcal{I}}$ we assign an element $k_i$ from ${{Z_p}^d}$ and set $k_1 = (0,\ldots,0)$. We will often write $0$ instead of $k_1$.

Let $({\mathcal{M}},{\circledast})$ be an algebra of $p^d \times p^d$-matrices whose entries are $\ell^1$-sequences and multiplication of two elements $A,B \in {\mathcal{M}}$ is given by $$({{A}\,{\circledast}\,{B}})_{i,j} = \sum_{l \in {\mathcal{I}}} {{A_{i,l}}\,\ast\,{B_{l,j}}}
   \qquad i,j \in{\mathcal{I}}\,.$$ The identity element ${\mbox{Id}}$ is a matrix with $\delta$ sequences on the diagonal.

\[thm1\] Let $${\mathcal{M}}_0 = {\Big\{ \, A \in {\mathcal{M}}\, \Big| \, A_{i,j} = \sum_{m \in {{Z_p}^d}}
   {\omega}^{{ m \, \cdot \, k_j}} a^{m,k_i - k_j}, a \in \ell^1 ~\text{and}~ i,j \in {\mathcal{I}}\, \Big\}}.$$ Then ${\mathcal{M}}_0$ is a subalgebra of ${\mathcal{M}}$.

Define a mapping $\phi \colon (\ell^1,{\natural}) \rightarrow ({\mathcal{M}},{\circledast})$ by $$\label{eq:map-phi}
   (\phi(a))_{i,j} = \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} a^{m,k_i - k_j}.$$ Then $\phi$ is linear, $(\phi(\delta))_{i,j} = \sum_{m \in {{Z_p}^d}}
{\omega}^{{ m \, \cdot \, k_j}} \delta^{m,k_i-k_j} = \delta$ if $i=j$ and zero otherwise. So $\phi(\delta) = {\mbox{Id}}$. We emphasize that the mapping $\phi$ has been motivated by the matrix $\hat{G}_0$ described in the previous section. For $i,j \in {\mathcal{I}}$, $$\begin{aligned}
  \big ( \phi({{a}\,{\natural}\,{b}}) \big )_{i,j}
  &=& \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}}
  ({{a}\,{\natural}\,{b}})^{m,k_i - k_j} = \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}}
  \sum_{l,s \in {{Z_p}^d}}
  {\omega}^{(m-l)\cdot s} {{a^{l,s}}\,\ast\,{b^{m-l,k_i- k_j-s}}} \\
  &=& \sum_{m,l,s \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j+s})} {\omega}^{{ -l \, \cdot \, s}}
  {{a^{l,s}}\,\ast\,{b^{m-l,k_i- k_j-s}}} \\
  &=& \sum_{m,l,s \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, s}} {\omega}^{-l \cdot (s-k_j)}
  {{a^{l,s-k_j}}\,\ast\,{b^{m-l,k_i-s}}}\\
  &=& \sum_{m,l,s \in {{Z_p}^d}} {\omega}^{{ l \, \cdot \, k_j}} {\omega}^{{ s \, \cdot \, (m-l)}}
  {{a^{l,s-k_j}}\,\ast\,{b^{m-l,k_i-s}}} \\
  &=& \sum_{s \in {{Z_p}^d}} {{\big ( \sum_{l \in {{Z_p}^d}}
  {\omega}^{{ l \, \cdot \, k_j}}a^{l,s-k_j} \big )}\,\ast\,{\big ( \sum_{m \in {{Z_p}^d}}
  {\omega}^{{ s \, \cdot \, (m-l)}} b^{m-l,k_i-s} \big )}} \\
  &=& \sum_{n \in {\mathcal{I}}} {{\big ( \sum_{m \in {{Z_p}^d}} {\omega}^{{ k_n \, \cdot \, m}}
  b^{m,k_i-k_n}\big)}\,\ast\,{\big ( \sum_{l \in {{Z_p}^d}} {\omega}^{{ l \, \cdot \, k_j}}
  a^{l,k_n-k_j} \big )}} \\
  &=& \sum_{n \in {\mathcal{I}}} {{\phi(b)_{i,n}}\,\ast\,{\phi(a)_{n,j}}} \;= \;
  \big ( {{\phi(b)}\,{\circledast}\,{\phi(a)}} \big )_{i,j}\,.\end{aligned}$$ Therefore $\phi$ is an anti-homomorphism, that is, $$\phi({{a}\,{\natural}\,{b}}) = {{\phi(b)}\,{\circledast}\,{\phi(a)}}.$$ Hence ${\mathcal{M}}_0$ is an algebra, being an image of an anti-homomorphism.

Before stating the main theorem, we explore properties of elements of ${\mathcal{M}}_0$. For $i,j \in {\mathcal{I}}$ and a matrix $A \in {\mathcal{M}}_0$ we define a new matrix $A(j,i)$ obtained from $A$ by substituting the $j$th row of $A$ with a vector of zeros having $\delta$ on the $i$th position, and the $i$th column with a column of zeros having $\delta$ on the $j$th position.

\[lem2\] Let $A \in \mathcal{M}_0$. Then

-   $\det (A)$ is a sequence supported on ${\mathbb{Z}^d}\times p{\mathbb{Z}^d}$.

-   $\det (A(1,i))$ is a sequence supported on ${\mathbb{Z}^d}\times (k_i + p{\mathbb{Z}^d})$ for $i \in {\mathcal{I}}$.

Let $S_N$ be the group of permutations of the set ${\mathcal{I}}$. Then $$\begin{aligned}
  \det(A) &=& \sum_{\sigma \in S_N } (-1)^{\sigma} \prod_{i=1}^{N}
  A_{\sigma(i),i}= \sum_{\sigma \in S_N} (-1)^{\sigma} \prod_{i=1}^{N}
  \Big (\sum_{m_i \in {{Z_p}^d}}{\omega}^{k_i \cdot m_i} a^{m_i,k_{\sigma(i)}-k_i}\Big ) \\
  &=& \sum_{\sigma \in S_N} (-1)^{\sigma}
  \sum_{m_1,\ldots,m_{N} \in {{Z_p}^d}} {\omega}^{\sum_{i=1}^{N} { m_i \, \cdot \, k_i}}
  \underbrace{a^{m_1,k_{\sigma(1)}-k_1} \ast \cdots \ast
  a^{m_N,k_{\sigma(N)}-k_N}}_{G_{m_1,\ldots,m_N}}.\end{aligned}$$ Since $\sigma$ is a permutation of ${\mathcal{I}}$, $$(k_{\sigma(1)}-k_1)+(k_{\sigma(2)}-k_2)+\cdots+(k_{\sigma(N)}-k_N)=0.$$ Therefore, by Lemma \[lem1\], $G_{m_1,\ldots,m_N}$ is a sequence supported on the coset $(\sum_{i \in {\mathcal{I}}}m_i+p{\mathbb{Z}^d}) \times p{\mathbb{Z}^d}$. Since $\sum_{i \in{\mathcal{I}}} m_i$ runs over all ${{Z_p}^d}$, we see that $\det(A)$ is supported on the coset ${\mathbb{Z}^d}\times p{\mathbb{Z}^d}$, i.e., $\det(A) = \det(A)^{\cdot,0}$.

In order to compute the support of $\det(A(1,i))$ for $i \in {\mathcal{I}}$, let $S_{N-1}$ denote the group of permutations of $\{2,\ldots,N
\}$. Then for $i=1,\ldots,N$, $$\begin{aligned}
  \det(A(1,i))
  &=& (-1)^{i+1} \sum_{\sigma \in S_{N-1}}(-1)^{\sigma}
  A_{\sigma(2),1} \ast \cdots \ast A_{\sigma(i),i-1}
  \ast A_{\sigma(i+1),i+1} \ast \cdots \ast A_{\sigma(N),N}\\
  &=& (-1)^{i+1} \sum_{\sigma \in S_{N-1}} (-1)^{\sigma}
  \sum_{m_2,\ldots,m_N \in {{Z_p}^d}} {\omega}^{{ m_2 \, \cdot \, k_1} + \cdots +
  { m_i \, \cdot \, k_{i-1}}
  + { m_{i+1} \, \cdot \, k_{i+1}} + \cdots + { m_{N} \, \cdot \, k_N}} \times \\
  &\times& \underbrace{a^{m_2,k_{\sigma(2)}-k_1} \ast \cdots
  \ast a^{m_i,k_{\sigma(i)}-k_{i-1}}
  \ast a^{m_{i+1},k_{\sigma(i+1)}-k_{i+1}} \ast \cdots \ast
  a^{m_N,k_{\sigma(N)}-k_N}}_{G_{m_2,\ldots,m_N}}.\end{aligned}$$ Since $\sigma$ is a permutation of $\{2,\ldots,N\}$, $$\begin{aligned}
  &  (k_{\sigma(2)}-k_1) + \cdots + (k_{\sigma(i)}-k_{i-1}) +
  (k_{\sigma(i+1)}-k_{i+1}) + \cdots + (k_{\sigma(N)}-k_N) & \\
  &= \; (k_{\sigma(2)} + \cdots + k_{\sigma(N)}) - (k_1+k_2+\cdots+k_N) + k_i &\\
  &= \; (k_{\sigma(2)} + \cdots + k_{\sigma(N)}) - (k_2+\cdots+k_N) + k_i \; =
  \;k_i\,.&\end{aligned}$$ Therefore, by Lemma \[lem1\], $G_{m_2,\ldots,m_N}$ is supported on $(\sum_{i=2}^{N} m_i + p{\mathbb{Z}^d}) \times (k_i + p{\mathbb{Z}^d})$, and since each $m_i$ runs over all ${{Z_p}^d}$, $\det(A(1,i))$ is supported on ${\mathbb{Z}^d}\times (k_i+p{\mathbb{Z}^d})$. That is, $\det(A(1,i)) = \det(A(1,i))^{\cdot,k_i}$.

Now we are in the position to state and prove the main result

\[th:wiener\][\[Wiener’s Lemma for ${\mathcal{M}}_0$\]]{} Let $A \in{\mathcal{M}}_0$. If $A$ is invertible in ${\mathcal{M}}$, then $B=A^{-1} \in {\mathcal{M}}_0$.

Since $A \in {\mathcal{M}}_0$ is invertible, $\det(A)$ is an invertible sequence in $(\ell^1,\ast)$, and there exists a matrix $\widetilde{B} \in {\mathcal{M}}$ such that ${{A}\,{\circledast}\,{\widetilde{B}}} = {\mbox{Id}}$. By Lemma \[lem2\], $\det(A) = \det(A)^{\cdot,0}$ and by Lemma \[lem1\] its inverse, $e = \det(A)^{-1}$, is also supported on the same coset, hence $e = e^{\cdot,0}$. By Cramer’s rule the inverse of $A$ is given by $$\widetilde{B}_{i,j} = {{\det(A(j,i))}\,\ast\,{e}}.$$ We see that by Lemma \[lem2\] (b), $\widetilde{B}_{i,1}$ is a sequence supported on ${\mathbb{Z}^d}\times (k_i+p{\mathbb{Z}^d})$. Let $b$ be a sequence defined by $$b = \widetilde{B}_{1,1}+\widetilde{B}_{2,1} + \ldots +
   \widetilde{B}_{N,1}.$$ Then $\widetilde{B}_{i,1} = \sum_{j \in {\mathcal{I}}} b^{k_j,k_i}$. Define a new matrix, denoted by $B$, as $$B_{i,j} = \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} b^{m,k_i-k_j}.$$ Then $B \in {\mathcal{M}}_0$ and we will show that $B=\widetilde{B}$, that is, $B$ is the inverse of $A$.

Since $\widetilde{B}$ is the inverse of $A$, $$\begin{aligned}
   {\mbox{Id}}_{i,1} & = & \big ( {{A}\,{\circledast}\,{\widetilde{B}}} \big )_{i,1}
   = \sum_{j \in {\mathcal{I}}} {{A_{i,j}}\,\ast\,{\widetilde{B}_{j,1}}} \\ &=&
   \sum_{j \in {\mathcal{I}}} \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}}
   {{a^{m,k_i-k_j}}\,\ast\,{\widetilde{B}_{j,1}}} \\
   &=& \sum_{j \in {\mathcal{I}}} \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} {{a^{m,k_i-k_j}}\,\ast\,{\big ( \sum_{n \in {{Z_p}^d}} b^{n,k_j} \big )}} \\ &=& \sum_{j \in {\mathcal{I}}}
   \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} \sum_{n \in {{Z_p}^d}}
   {{a^{m,k_i-k_j}}\,\ast\,{b^{n,k_j}}} \\
   &=& \sum_{m \in {{Z_p}^d}}\sum_{j \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}}
   {\omega}^{{ (m-n) \, \cdot \, k_j}} {{a^{m-n,k_i-k_j}}\,\ast\,{b^{n,k_j}}} \\ &=&
   \sum_{m \in {{Z_p}^d}}G(m,k_i),\end{aligned}$$ where $G(m,k_i) = \sum_{j \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}} {\omega}^{{ (m-n) \, \cdot \, k_j}}
 a^{m-n,k_i-k_j} \ast b^{n,k_j}$ is a sequence supported on $(m+p{\mathbb{Z}}) \times (k_i+p{\mathbb{Z}})$. Therefore, $G(k_1,k_1) = \delta$ and $G(m,k_i) = 0$ for $m \neq k_1$ and $i \neq 1$. Using the above identity we will show that ${{A}\,{\circledast}\,{B}} = {\mbox{Id}}$, and by the uniqueness of the inverse we will conclude that $B=\widetilde{B}$: $$\begin{aligned}
  & & \big ( {{A}\,{\circledast}\,{B}} \big )_{i,j} \; = \; \sum_{s \in {\mathcal{I}}} A_{i,s}
  \ast B_{s,j} \; = \\ &=& \sum_{s \in {\mathcal{I}}} \Big ( \sum_{m \in {{Z_p}^d}}
  {\omega}^{{ m \, \cdot \, k_s}} a^{m,k_i-k_s} \Big) \ast \Big ( \sum_{n \in {{Z_p}^d}}
  {\omega}^{{ n \, \cdot \, k_j}} b^{n,k_s-k_j} \Big ) \\
  &=& \sum_{m \in {{Z_p}^d}} \sum_{s \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_s}}
  {\omega}^{{ n \, \cdot \, k_j}} a^{m,k_i-k_s} \ast b^{n,k_s-k_j}\\
  &=& \sum_{m \in {{Z_p}^d}} \sum_{s \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}} {\omega}^{{ (k_s+k_j) \, \cdot \, m}}
  {\omega}^{{ n \, \cdot \, k_j}} a^{m,k_i-k_j-k_s} \ast b^{n,k_s}\\ &=&
  \sum_{m \in {{Z_p}^d}} \sum_{s \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}} {\omega}^{{ (k_s+k_j) \, \cdot \, (m-n)}}
  {\omega}^{{ n \, \cdot \, k_j}} a^{m-n,(k_i-k_j)-k_s} \ast b^{n,k_s} \\
  &=& \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} \sum_{s \in {\mathcal{I}}} \sum_{n \in {{Z_p}^d}}
  {\omega}^{{ (m-n) \, \cdot \, k_s}} a^{m-n,(k_i-k_j)-k_s} \ast b^{n,k_s} \\
  &=& \sum_{m \in {{Z_p}^d}} {\omega}^{{ m \, \cdot \, k_j}} G(m,k_i-k_j) \; = \;
  \left \{ \begin{array}{cc}
     \delta & k_i - k_j = k_1 ~ \Leftrightarrow ~ i=j;\\ [.2cm]
     0 & k_i - k_j \neq k_1 ~ \Leftrightarrow ~ i \neq j;
  \end{array} \right.\end{aligned}$$ Hence, ${{A}\,{\circledast}\,{B}} =I$.

Theorem \[th:wiener\] provides the key result to study invertibility of twisted convolution. Indeed, for a given sequence $a$ in $\ell^1$ we look at the corresponding matrix $A = \phi(a)$ as defined in (\[eq:map-phi\]). If $A$ is invertible in $({\mathcal{M}},{\circledast})$, which can be checked showing that the determinant is invertible in $(\ell^1,\ast)$, then its inverse $A^{-1}$ is of the form $\phi(b)$ for another element $b$ in $\ell^1$. This element $b$, in turn, provides the inverse of $a$ in $(\ell^1,{\natural})$.

The approach is constructive in the sense that algebraic methods such as Cramer’s Rule can be applied to find the inverse of $A$. Then, the sequence $b$ can simply be read from the entries of $A^{-1}$ according to the mapping $\phi$. In particular for small $p$ and $d$ this method leads to fast inversion schemes for the twisted convolution operator. In the last section we will show explicitly how this works in the case of $d=1$.

Twisted convolution and Gabor analysis
======================================

Central objects in time frequency analysis are modulation and translation operators. Although most of the upcoming notation can be given in the more general setting of locally compact Abelian groups we restrict ourselves to ${{\mathbb{R}}^d}$ in order to simplify the readability of this article.

For $x,{\omega}\in{{\mathbb{R}}^d}$ we define the translation operator and the modulation operator on $L^2({{\mathbb{R}}^d})$ by $$\begin{aligned}
T_x f(\cdot) &=& f(\cdot - x)\,, \\
M_{\omega}f(\cdot) &=& e^{2\pi i {\omega}\cdot} f(\cdot)\,,\end{aligned}$$ respectively. Many technical details in time-frequency analysis are linked to the commutation law of the translation and modulation operator, namely, $$\label{eq:commlaw}
 M_{\omega}T_x\, = \, e^{2\pi i { x \, \cdot \, {\omega}}}T_x M_{\omega}\,.$$ The time-frequency shift for $x,{\omega}\in{{\mathbb{R}}^d}$ is denoted by $$\pi(x,{\omega}) = T_x M_{\omega}.$$ It follows from (\[eq:commlaw\]) that $$\label{eq:commlaw2}
\pi(x_1,{\omega}_1)\pi(x_2,{\omega}_2) \, = \, e^{2\pi i { x_2 \, \cdot \, {\omega}_1}}
\pi(x_1+x_2,{\omega}_1+{\omega}_2)\,.$$ This shows that time-frequency shifts almost allow a group structure. Incorporating the additional phase factor into a more extended group law leads to the so-called Heissenberg group. For more details about this topic, the reader is referred to [@F89].

Gabor analysis deals with the problem of decomposing and reconstructing signals according to a special basis system which consists of regular time-frequency shifts of a single so-called window function [@FS98; @FS03]. Let ${\Lambda}$ be a time-frequency lattice, i.e., a discrete subgroup of the time-frequency plane ${{\mathbb{R}}^{2d}}$, and let $g$ be in $L^2({{\mathbb{R}}^d})$. Then we define a Gabor system ${\mathcal{G}}(g,{\Lambda})$ by $${\mathcal{G}}(g,{\Lambda}) \, = \, {\Big\{ \, \pi({\lambda})g \, \Big| \, {\lambda}\in{\Lambda}\, \Big\}}\,.$$ We associate with this Gabor system the positive operator $$S:f\in L^2 \rightarrow Sf = \sum_{{\lambda}\in{\Lambda}}
   {\langle f,\pi({\lambda})g\rangle}\pi({\lambda})g \,.$$ If the operator $S$ is bounded and invertible on $L^2({{\mathbb{R}}^d})$, then ${\mathcal{G}}(g,{\Lambda})$ is called a frame and $S$ the associated frame operator, cf. [@CH03].

Many studies in Gabor analysis are devoted to the frame operator [@Gro01]. In what follows we will describe the so-called Janssen representation of such operators. To this end we need the notion of the adjoint lattice, i.e., $${{\Lambda}^\circ}\, = \, {\Big\{ \, {{\lambda}^\circ}\in{{\mathbb{R}}^{2d}}\, \Big| \, \pi({\lambda})\pi({{\lambda}^\circ})=
   \pi({{\lambda}^\circ})\pi({\lambda}),\, {\lambda}\in{\Lambda}\, \Big\}}\,.$$ In [@DLL95; @FK98; @Jan95] it is shown that the frame operator $S$ satisfies Janssen representation, $$\label{eq:jans-repr}
   S \, = \, \sum_{{{\lambda}^\circ}\in{{\Lambda}^\circ}} {\langle g,\pi({{\lambda}^\circ})g\rangle}\pi({{\lambda}^\circ})\,.$$ At this point, the question arises if we can deduce the invertibility of the operator $S$ from the Janssen coefficients $({\langle g,\pi({{\lambda}^\circ})g\rangle})$. It is known from frame theory that if $S$ is invertible, then its inverse is of the same type, that is, it also has a Janssen representation.

In order to better understand the main ingredients of this problem we transfer the model to an operator algebra. To this end we restrict our discussion to so-called separable lattices of the form $${\Lambda}\, = \, {\alpha}{\mathbb{Z}^d}\times {\beta}{\mathbb{Z}^d}$$ for some fixed positive numbers ${\alpha}$ and ${\beta}$. An easy computation based on (\[eq:commlaw2\]) shows that $${{\Lambda}^\circ}\, = \, {\beta}^{-1} {\mathbb{Z}^d}\times {\alpha}^{-1}  {\mathbb{Z}^d}\,.$$

We define the operator algebra ${\mathcal{A}}$ as in [@GL03] by $${\mathcal{A}}\, = \, {\Big\{ \, S = \sum_{k,l\in{\mathbb{Z}^d}}a_{k,l}
       \pi({\beta}^{-1}k,{\alpha}^{-1}l) \, \Big| \, a=(a_{k,l})\in\ell^1({\mathbb{Z}^{2d}}) \, \Big\}}\,.$$ The restriction to $\ell^1$-sequences guarantees absolute convergence of the sum of time-frequency shifts. Let ${\kappa}$ be the mapping $${\kappa}:a\in\ell^1 \rightarrow {\kappa}(a) =  \sum_{k,l\in{\mathbb{Z}^d}}a_{k,l}
       \pi({\beta}^{-1}k,{\alpha}^{-1}l)\in{\mathcal{A}}\,.$$ Then, as already observed in [@Jan95], we have $${\kappa}(a){\kappa}(b) \, = \, {\kappa}({{a}\,{\natural}\,{b}})$$ and ${\kappa}(\delta) = {\mbox{Id}}$ where $\delta$ and ${\mbox{Id}}$ denote the Dirac sequence and the identity operator, respectively. Both represent the unit element of the corresponding algebra. It follows that ${\kappa}$ is an algebra homomorphism from $(\ell^1({\mathbb{Z}^{2d}}),{\natural})$ to ${\mathcal{A}}$, and invertibility of an element in ${\mathcal{A}}$ can be transferred to the invertibility of the associated $\ell^1$-sequence with respect to the twisted convolution.

It is important to observe, that all the results go through also for weighted $\ell^1$-spaces. These facts are used to design dual Gabor windows of a special type, cf. [@GL03].

In the following section we give an example of how this approach can be explicitly used in Gabor analysis of one-dimensional signals.

[**Remark.**]{} The above results, with the help of metaplectic operators, carry over to the more general class of lattices, called symplectic lattices. A lattice ${\Lambda}_s \subseteq {{\mathbb{R}}^{2d}}$ is called symplectic, if one can write ${\Lambda}_s = {\mathcal{D}}{\Lambda}$ where ${\Lambda}$ is a separable lattice and ${\mathcal{D}}\in GL_{2d}({\mathbb{R}})$. To every ${\mathcal{D}}\in
GL_{2d}({\mathbb{R}})$, there corresponds a unitary operator $\mu({\mathcal{D}})$, called metaplectic, acting on $L^2({{\mathbb{R}}^d})$. One can show that a Gabor system on a symplectic lattice is unitary equivalent to a Gabor system on a separable lattice under $\mu({\mathcal{D}})$, and $$S_{g}^{{\Lambda}_s} = \mu({\mathcal{D}})^{-1} S_{\mu({\mathcal{D}})g}^{{\Lambda}} \mu({\mathcal{D}}).$$ Hence, to analyze the invertibility of a frame operator $S$ associated to the window function $g \in L^2({{\mathbb{R}}^d})$ and symplectic lattice ${\Lambda}_s$, it suffices to analyze a frame operator associated to $\mu({\mathcal{D}})g$ and a separable lattice ${\Lambda}$. For more details see [@Gro01].

Application to one-dimensional signal space
===========================================

In this section, we briefly describe how the presented inversion scheme applies to Gabor frame operators in a one-dimensional setting. A more detailed discussion also for finite dimensional signals is described in [@MWE05].

Assume $d=1$. Let $a$ be in $\ell^1({\mathbb{Z}}^2)$ and ${\alpha}, {\beta}$ be constants such that ${\alpha}{\beta}= p/q$ with $p,q$ relative prime. Set $${\kappa}(a) = \sum_{k,l\in{\mathbb{Z}}}a_{k,l}\pi({\beta}^{-1}k,{\alpha}^{-1}l)\,.$$ In order to verify if ${\kappa}(a)$ is invertible on $L^2({\mathbb{R}})$ we simply look at the coefficient sequence $a$ and check whether $a$ is invertible in $(\ell^1({\mathbb{Z}}^2),{\natural})$. To this end, we apply the above results and switch to the matrix $A$ whose entries are defined by $$A_{i,j} = \sum_{m=0}^{p-1} {\omega}^{mj}a^{m,i-j}\,,$$ with ${\omega}= e^{2\pi i q/p}$. Next, we need to show that the matrix $A$ is invertible in $({\mathcal{M}},{\circledast})$. For example, we can calculate the determinate which is a sequence in $\ell^1$ and show that it is invertible in $(\ell^1,\ast)$.

Assume that the determinant of $A$ is invertible. We denote its inverse by $e$. By Cramer’s Rule, we compute the first column of the inverse matrix $B$ of $A$ as $$B_{k,0} = {{\det A(0,k)}\,\ast\,{e}}\,,$$ for $k=0,\dots,p-1$. Then $$b = \sum_{k=0}^{p-1}B_{k,0}$$ provides the inverse sequence of $a$ which, in turns, gives ${\kappa}(a)^{-1} = {\kappa}(b)$.

Note that for $p=1$, the twisted convolution turn into normal convolution and we can simply apply the standard Fourier inversion scheme of sequences in $(\ell^1({\mathbb{Z}}^2),\ast)$ since in this case the matrix $A$ reduces to the sequence $a$.

Acknowledgements {#acknowledgements .unnumbered}
================

The authors gratefully acknowledge support from the Ollendorff Minerva Center and from the European Union’s Human Potential Programme, under the contract HPRN-CT-2003-00285 (HASSIP). We would also like to thank Karlheinz Gr[ö]{}chenig and Yehoshua Y. Zeevi for many fruitful discussions.

[^1]: Dept. of Electrical Engineering, Technion–Israel Institute of Technology, 32000 Haifa, Israel. Tel.: +972-4-8293256, Fax.: +972-4-8295757, Email: `yonina@ee.technion.ac.il`

[^2]: Faculty of Math., University of Vienna, 1090 Vienna, Austria. Tel.: +43-1-4277-50693, Fax.: +43-1-4277-50690, Email: `ewa.matusiak@univie.ac.at`, `tobias.werther@univie.ac.at`.
