# Convergence of reputations under indirect reciprocity

Bryce Morsky<EMAIL_ADDRESS>Department of Mathematics, Florida State
University, Tallahassee, FL, USA  Department of Biology, University of
Pennsylvania, Philadelphia, PA, USA  Joshua B. Plotkin<EMAIL_ADDRESS>Department of Biology, University of Pennsylvania, Philadelphia, PA, USA  Erol
Akçay<EMAIL_ADDRESS>Department of Biology, University of Pennsylvania,
Philadelphia, PA, USA

###### Abstract

Previous research has shown how indirect reciprocity can promote cooperation
through evolutionary game theoretic models. Most work in this field assumes a
separation of time-scales: individuals’ reputations equilibrate at a fast time
scale for given frequencies of strategies while the strategies change slowly
according to the replicator dynamics. Much of the previous research has
focused on the behaviour and stability of equilibria for the replicator
dynamics. Here we focus on the underlying reputational dynamics that occur on
a fast time scale. We describe reputational dynamics as systems of
differential equations and conduct stability analyses on their equilibria. We
prove that reputations converge to a unique equilibrium for each of the five
standard norms whether assessments are public or private. These results
confirm a crucial but previously unconfirmed assumption underlying the theory
of indirect reciprocity for the most studied set of norms.

Keywords: cooperation, evolutionary game theory, indirect reciprocity,
reputations, social norms

##  1 Introduction

Indirect reciprocity is an important mechanism to foster cooperation.
Theoretical studies have extended an evolutionary game theoretic model of the
Prisoner’s Dilemma game (also termed the Donation game) by adding a system of
reputations and a population of Discriminators who defect against “bad”
individuals and cooperate with “good” ones [4, 6, 11, 13, 14, 15, 19]. To
determine who is good and who is bad, interactions between pairs of
individuals are observed. To assess a donor’s reputation (as good or bad), an
observer may consider the action the donor took (to cooperate or defect), the
reputation of the recipient with the observer (either good or bad), and a
social norm. The social norms provide the rules of how to assess what the
observer observed. For all norms, a donor is assessed as good if they
cooperate with a good donor. This is a minimum requirement to promote
cooperation. However, the norms will differ on their recommendations for other
scenarios. There are five social norms that are frequently studied: Scoring
[23], Shunning [22], Staying [9], Simple Standing [7], and Stern Judging [18].
Scoring was the first norm studied, and under it a donor is considered good if
they cooperate and bad if they defect. Assessments under Scoring do not depend
on the reputation of the recipient, but this norm leads to a population that
only ever defects. Thus, attention shifted to higher order norms that factor
in the reputation of the recipient (Shunning, Staying, Simple Standing, and
Stern Judging). Under the Stern Judging norm, donors are assessed as good if
they cooperate with good recipients and defect with bad ones. Conversely, they
are assessed as bad if they defect with good recipients and cooperate with bad
ones. In the initial work studying these norms, reputations were generally
assumed to be assessed publicly wherein there is a shared reputational system
[2, 3, 12] and all individuals agree on each other’s reputation. Private
reputations were later explored [15], which allow for individuals to hold
private information and disagree about the reputations of others. Conflict
between different opinions of individuals can undermine the reputational
system and thus cooperation. These five norms and two methods of assessment
(public and private) form the core set of theoretical models of indirect
reciprocity. Additionally, there are a great many models extending this
framework including noisy and incomplete information [5], individuals’
emotions [17] and individuals’ reasoning to account for errors and
discrepancies in reputations [8, 16] to name a few.

Despite a wide range of assumptions about assessment and game play, the above
models generally share the assumption that the dynamics reputation and
strategies operate at two different time scales. Reputations are assumed to
equilibrate rapidly while strategies change much more slowly. This assumption
can be justified if each individual undergoes many interactions during its
lifetime (if replicator dynamics model a birth-death process, or simply update
infrequently). A further justification is that individuals cannot fully assess
the payoffs of their strategies (and thus not compare and imitate) until
reputations have reached an equilibrium. As a theory building strategy, this
assumption allows the models to account for the full incentive effects through
reputations of a strategy composition of the population. It also makes the
theory analytically tractable.

Under this separation of time-scale assumption, the strategies of individuals
change in response to payoffs that are computed for the frequencies of the
types of individuals while assuming that their reputations are at the
equilibrium levels given the strategy frequencies. Though equilibria of the
reputational system were found previously and used to analyze the replicator
dynamics that govern the change in strategies, whether or not they converged
to these equilibria has been understudied. Convergence of reputations to
unique equilibria has only been proved in a few cases such as for models that
incorporate reasoning [8, 16]. However, convergence in some situations is
conditional on the parameter values chosen [16], and thus need not hold
generally. Thus, it is an open and key question as to whether or not
reputations converge. Here, we have proven that reputations in the standard
indirect reciprocity model do indeed converge to unique equilibria for the
five common norms and both public and private assessments of reputations. We
do this by representing the reputational dynamics as a system of ordinary
differential equations and analyse the stability of the equilibria of these
systems. This setup places some assumptions on the reputation dynamics such as
the population being infinite and time being continuous. However, these are
frequently assumed in mathematical models of indirect reciprocity. So long as
the population is large and dynamics occur in short intervals of time. In the
methods section, we define the system of ordinary differential equations that
model the reputational dynamics, and in the results section analyze the
stability of their equilibria.

##  2 Methods

Consider three types of players each playing a specific strategy in the
donation game. AllC (always cooperate) players are those who always _intend_
to cooperate regardless of the reputation of the recipient, and $x$ is their
frequency in the population. Note that AllC players only intend to cooperate:
they don’t always successfully do so. As discussed below, we assume — as is
standard in the literature — that errors may occur when players attempt to
cooperate by which they unintentionally defect. AllD players always defect,
and their frequency in the population is $y$. Note that there is no
possibility for an AllD player to accidentally cooperate. The third and final
type of player are Discriminators, who intend to cooperate with good
recipients and defect against bad ones. They thus act as punishers of “bad
behaviour” (as determined by the social norm). Their frequency in the
population is $z$, and we have $x+y+z=1$. Since reputations converge rapidly,
i.e. before strategies can change, $x$, $y$, and $z$ will be constants in our
analyses.

Errors in action and assessment are assumed in many models of indirect
reciprocity. Let $\tfrac{1}{2}>e_{1}>0$ be the probability that a donor who
intends to cooperate defects by mistake. Further, let $\tfrac{1}{2}>e_{2}>0$
be the probability that there is an error in the assessment of the reputation
of the donor. That is to say, with probability $e_{2}$, the observer assigns
the _opposite_ reputation to the donor than they intended to. Define
$\epsilon=(1-e_{1})(1-e_{2})+e_{1}e_{2}$ as the probability that an individual
who intends to cooperate is observed doing so. We will use $\epsilon$
throughout our analysis rather than $e_{1}$. Also, we write $e=e_{2}$ to
further simplify our notation. The parameters $\epsilon$ and $e$ along with
the social norm and whether or not assessment are public will thus determine
reputations.

|  Donor’s action / recipient’s reputation
---|---
Social norm | $C/G$ | $D/G$ | $C/B$ | $D/B$
Scoring | $G$ | $B$ | $G$ | $B$
Shunning | $G$ | $B$ | $B$ | $B$
Simple Standing | $G$ | $B$ | $G$ | $G$
Staying | $G$ | $B$ | — | —
Stern Judging | $G$ | $B$ | $B$ | $G$
Table 1: Assessments of the donor (either $G$ or $B$ for good or bad) given
the donor’s action (either $C$ or $D$ for cooperate or defect), recipient’s
reputation ($G$ or $B$), and the social norm. The dash under Staying implies
that the reputation of the donor is not updated when they interact with a
recipient with a bad reputation.

Social norms determine what actions are good and what bad given the reputation
of the donor. Five important norms frequently studied in the literature are:
Scoring, Shunning, Staying, Simple Standing, and Stern Judging. The rules for
these norms are represented in Table 1. For example, under Simple Standing, a
donor is assessed as good if they cooperate with a good recipient, and bad if
they do not. And, they’re assessed as good when they interact with a bad
recipient, regardless of whether or not they cooperate. Note that due to the
error in assessment, it is possible for an observer to assess a donor who
interacts with a bad recipient as bad. However, in models where players can
factor in error rates and thereby reason about the intention of the donor,
this cannot happen [8, 16].

The state variables in our analyses of the reputational dynamics are the
fraction of players of each type that are good. Thus, $g_{x}$ and $1-g_{x}$
are the frequencies of AllC players with good and bad reputations,
respectively. Likewise $g_{y}$ and $1-g_{y}$ are the frequencies of AllD
players with good and bad reputations, respectively. Finally, $g_{z}$ and
$1-g_{z}$ are the frequencies of Discriminators with good and bad reputations,
respectively. The total frequency of good players in the population is
$g=xg_{x}+yg_{y}+zg_{z}$.

Reputations can be assessed publicly or privately, which impact the assessment
of the reputations of Discriminators because Discriminators’ behaviours are
determined by the reputation the recipient has with them. Thus, if this
differs between the observer and a donor Discriminator, we need to know the
frequency with which two players agree that a recipient is good, denoted
$g_{2}$. The probability that two AllC players are good is defined as
$g_{x2}$. $g_{y2}$ and $g_{z2}$ for AllD players and Discriminators are
defined similarly. Thus, $g_{2}=xg_{x2}+yg_{y2}+zg_{z2}$. Under private
assessment of reputations, $g_{x2}$, $g_{y2}$, and $g_{z2}$ will be state
variables in addition to $g_{x}$, $g_{y}$, and $g_{z}$.

As in previous models, we assume that reputations change by a good individual
being reassessed as bad or a bad individual being reassessed as good [15, 19].
Let $g_{i}^{+}$ be the probability that a bad individual of type $i$ is
reassessed as good, and $g_{i}^{-}$ be the probability that a good individual
of type $i$ is reassessed as good. To represent this process as a system of
differential equations, we define $\dot{g}_{i}=g_{i}^{+}-g_{i}^{-}$ by
assuming a limiting process. We are thus able to convert a discrete process
into a continuous one. We use the same values of $g_{i}^{+}$ and $g_{i}^{-}$
from [15, 19]. The reputational systems under public assessment for the five
norms are thus:

$\begin{rcases}\dot{g}_{x}=\epsilon-g_{x}\\\ \dot{g}_{y}=e-g_{y}\\\ \dot{g}_{z}=\epsilon g+e(1-g)-g_{z}\end{rcases}\text{Scoring},$ (1a) |  $\begin{rcases}\dot{g}_{x}=\epsilon g+e(1-g)-g_{x}\\\ \dot{g}_{y}=e-g_{y}\\\ \dot{g}_{z}=\epsilon g+e(1-g)-g_{z}\end{rcases}\text{Shunning},$ (1b)
---|---
$\begin{rcases}\dot{g}_{x}=(\epsilon-g_{x})g\\\ \dot{g}_{y}=(e-g_{y})g\\\ \dot{g}_{z}=(\epsilon-g_{z})g\end{rcases}\text{Staying},$ (1c) |  $\begin{rcases}\dot{g}_{x}=\epsilon g+(1-e)(1-g)-g_{x}\\\ \dot{g}_{y}=eg+(1-e)(1-g)-g_{y}\\\ \dot{g}_{z}=\epsilon g+(1-e)(1-g)-g_{z}\end{rcases}\text{Simple Standing},$ (1d)

$\begin{rcases}\dot{g}_{x}=\epsilon g+(1-\epsilon)(1-g)-g_{x}\\\
\dot{g}_{y}=eg+(1-e)(1-g)-g_{y}\\\ \dot{g}_{z}=\epsilon
g+(1-e)(1-g)-g_{z}\end{rcases}\text{Stern Judging}.$ (1e)
---

And for private assessment of reputations, the systems are as follows:

$\begin{rcases}\dot{g}_{x}=\epsilon g+e(1-g)-g_{x}\\\ \dot{g}_{y}=e-g_{y}\\\ \dot{g}_{z}=\epsilon g_{2}+e(1-g_{2})-g_{z}\\\ \dot{g}_{x2}=(\epsilon g+e(1-g))g_{x}-g_{x2}\\\ \dot{g}_{y2}=eg_{y}-g_{y2}\\\ \dot{g}_{z2}=(\epsilon g_{2}+e(1-g_{2}))g_{z}-g_{z2}\end{rcases}\text{Shunning},$ (2a) |  $\begin{rcases}\dot{g}_{x}=(\epsilon-g_{x})g\\\ \dot{g}_{y}=(e-g_{y})g\\\ \dot{g}_{z}=\epsilon g_{2}+e(g-g_{2})-g_{z}g\\\ \dot{g}_{x2}=(\epsilon g_{x}-g_{x2})g\\\ \dot{g}_{y2}=(eg_{y}-g_{y2})g\\\ \dot{g}_{z2}=(\epsilon g_{2}+e(g-g_{2}))g_{z}-g_{z2}g\end{rcases}\text{Staying},$ (2b)
---|---

$\begin{rcases}\dot{g}_{x}=\epsilon g+(1-e)(1-g)-g_{x}\\\
\dot{g}_{y}=eg+(1-e)(1-g)-g_{y}\\\ \dot{g}_{z}=\epsilon
g_{2}+e(g-g_{2})+(1-e)(1-g)-g_{z}\\\ \dot{g}_{x2}=(\epsilon
g+(1-e)(1-g))g_{x}-g_{x2}\\\ \dot{g}_{y2}=(eg+(1-e)(1-g))g_{y}-g_{y2}\\\
\dot{g}_{z2}=(\epsilon
g_{2}+e(g-g_{2})+(1-e)(1-g))g_{z}-g_{z2}\end{rcases}\text{Simple Standing},$
(2c)
---
$\begin{rcases}\dot{g}_{x}=\epsilon g+(1-\epsilon)(1-g)-g_{x}\\\
\dot{g}_{y}=eg+(1-e)(1-g)-g_{y}\\\
\dot{g}_{z}=(1-2g)(1-e)+g+(\epsilon-e)(2g_{2}-g)-g_{z}\\\
\dot{g}_{x2}=(\epsilon g+(1-\epsilon)(1-g))g_{x}-g_{x2}\\\
\dot{g}_{y2}=(eg+(1-e)(1-g))g_{y}-g_{y2}\\\
\dot{g}_{z2}=((1-2g)(1-e)+g+(\epsilon-e)(2g_{2}-g))g_{z}-g_{z2}\end{rcases}\text{Stern
Judging}.$ (2d)

Since the reputation of the recipient is irrelevant for Scoring, the
reputation dynamics are the same whether assessments are public or private.

To be more explicit on how these equations are derived, consider the dynamics
for AllC under Simple Standing. $g_{x}$ increases when a bad AllC player is
reassessed as good, which occurs with probability
$g_{x}^{+}=(1-g_{x})(\epsilon g+(1-e)(1-g))$. A bad AllC player is selected
with probability $1-g_{x}$. With probabilities $g$ and $1-g$ they pair with a
good and bad recipient, respectively. When paired with a good recipient, the
bad AllC player is reassessed as good with probability $\epsilon$. When paired
with a good AllC player, they are reassessed as good with probability $1-e$.
In a similarly fashion a good AllC player is reassessed as bad with
probability $g_{x}^{-}=g_{x}((1-\epsilon)g+e(1-g))$. Simplifying we have
$g_{x}^{+}-g_{x}^{-}=\epsilon g+(1-e)g-g_{x}$, to which we define
$\dot{g}_{x}$. The reputational dynamics for $g_{y}$ can be found similarly.
Under public assessment of reputations, $g_{z}$ is also found similarly.
However, under private assessment, one has to take care of how the
Discriminator donor and observer view the reputations of the recipient. If
they both agree that they’re good, then the donor will intend to cooperate and
the observer will evaluate them as if they’re interacting with a good
recipient. This occurs with probability $g_{2}$ and the donor will then be
assessed as good with probability $\epsilon$. With probability $g-g_{2}$ the
donor believes that the recipient is bad and so defects, but the observer
believes that they’re good. A donor who intends to defect against a good
recipient will be assessed as good only if an error in assessment occurs, i.e.
with probability $e$. Finally, with probability $1-g$, the observer believes
that the recipient is bad, and thus will assess the donor as good so long as
there is no error in assessment, i.e. with probability $1-e$. Thus, a bad
Discriminator will be reassessed as good with probability
$g_{z}^{+}=(1-g_{z})(\epsilon g_{2}+e(g-g_{2})+(1-e)(1-g))$. $g_{z}^{-}$ is
found in a similar way. However, we consider the probabilities that the donor
is bad. For example, if both donor and observer believe that the recipient is
good, which happens with probability $g_{2}$, then the donor is assessed as
bad with probability $1-\epsilon$. The other terms are found in a similar way
giving us $g_{z}^{-}=g_{z}((1-\epsilon)g_{2}+(1-e)(g-g_{2})+e(1-g))$ and
$\dot{g}_{z}=g_{z}^{+}-g_{z}^{-}=\epsilon g_{2}+e(g_{2}-g)+(1-e)(1-g)$.

Continuing with the example of Simple Standing under private assessment of
reputations, $g_{x}-g_{x2}$ is the probability that one player believes that
an AllC player is good and another believes that they are bad. Thus, $g_{x2}$
increases when such an AllC player is reassessed as good, which happens with
probability $g_{x2}^{+}=(g_{x}-g_{x2})(\epsilon g+(1-e)(1-g))$. In a similar
way, we can calculate the probability that $g_{x2}$ decreases as
$g_{x2}^{-}=g_{x2}((1-\epsilon)g+e(1-g))$, which gives us
$\dot{g}_{x2}=g_{x2}^{+}-g_{x2}^{-}=(\epsilon g+(1-e)(1-g))g_{x}-g_{x2}$.
$g_{y2}^{+}$, $g_{y2}^{-}$, $\dot{g}_{y2}$, $g_{z2}^{+}$, $g_{z2}^{-}$, and
$\dot{g}_{z2}$ are all computed similarly.

##  3 Results

###  3.1 Public Assessment

First consider an analysis of the case of public assessment of reputations.
Equilibria have previously been found in the literature [19], but here we show
that reputations converge to a unique equilibrium for each norm. Beginning
with Scoring, there is only one equilibrium frequency of good individuals,
namely

$g^{*}=\frac{\epsilon x+e(1-x)}{1-(\epsilon-e)z},$ (3)

which is defined across the simplex and for all error rates (as will all
equilibria here). The Jacobian of the system of ODEs is

$\mathbf{J}=\begin{pmatrix}-1&0&0\\\ 0&-1&0\\\
(\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z-1\\\ \end{pmatrix},$ (4)

which has eigenvalues $\lambda_{1}=\lambda_{2}=-1$ and
$\lambda_{3}=(\epsilon-e)z-1<0$. Note that $\mathbf{J}$ is not a function of
$g$, which will be the case under public assessment for all norms but Staying.
Since the eigenvalues are negative and $g^{*}$ is the sole equilibrium,
$g^{*}$ is stable. Additionally, since assessments under Scoring do not depend
upon the reputation of the recipient, there is no difference in Scoring
between public and private assessments and thus these results hold for both.

For Shunning, the sole equilibrium frequency of good individuals is

$g^{*}=\frac{e}{1-(\epsilon-e)(1-y)},$ (5)

and the Jacobian of the system is

$\mathbf{J}=\begin{pmatrix}(\epsilon-e)x-1&(\epsilon-e)y&(\epsilon-e)z\\\
0&-1&0\\\ (\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z-1\\\ \end{pmatrix}.$ (6)

It has eigenvalues $\lambda_{1}=\lambda_{2}=-1$ and
$\lambda_{3}=(\epsilon-e)(1-y)-1<0$, and thus $g^{*}$ is stable.

For Staying, there are two equilibria: $g^{*}=0$ and $g^{*}=\epsilon(1-y)+ey$,
and in the latter case $g_{x}^{*}=g_{z}^{*}=\epsilon$ and $g_{y}^{*}=e$.
Subbing these solutions into the Jacobian gives us the following matrices:

$\mathbf{J}(0)=\begin{pmatrix}\epsilon x&\epsilon y&\epsilon z\\\ ex&ey&ez\\\
\epsilon x&\epsilon y&\epsilon z\\\ \end{pmatrix},$ (7a)
$\mathbf{J}(\epsilon(1-y)+ey)=\begin{pmatrix}-\epsilon(1-y)-ey&0&0\\\
0&-\epsilon(1-y)-ey&0\\\ 0&0&-\epsilon(1-y)-ey\\\ \end{pmatrix}.$ (7b)

The eigenvalues for Equation 7a are $\lambda_{1}=\lambda_{2}=0$ and
$\lambda_{3}=\epsilon(1-y)+ey>0$, and thus $g^{*}=0$ is unstable. The
eigenvalues for Equation 7b are
$\lambda_{1}=\lambda_{2}=\lambda_{3}=-(1-y)\epsilon-ey<0$, and thus
$g^{*}=\epsilon(1-y)+ey$ is stable.

For Simple Standing, we have the sole equilibrium

$g^{*}=\frac{1-e}{1-e+1-\epsilon(1-y)-ey}.$ (8)

The Jacobian of the system is

$\mathbf{J}=\begin{pmatrix}(\epsilon+e-1)x-1&(\epsilon+e-1)y&(\epsilon+e-1)z\\\
(2e-1)x&(2e-1)y-1&(2e-1)z\\\
(\epsilon+e-1)x&(\epsilon+e-1)y&(\epsilon+e-1)z-1\\\ \end{pmatrix},$ (9)

which has eigenvalues $\lambda_{1}=\lambda_{2}=-1$ and
$\lambda_{3}=e-1+\epsilon(1-y)+ey-1<0$. Therefore, $g^{*}$ is stable.

And, finally, for Stern Judging, we have the sole equilibrium

$g^{*}=\frac{1-\epsilon x-e(1-x)}{1-\epsilon x-e(1-x)+1-\epsilon(1-y)-ey}.$
(10)

The Jacobian of the system is

$\mathbf{J}=\begin{pmatrix}(2\epsilon-1)x-1&(2\epsilon-1)y&(2\epsilon-1)z\\\
(2e-1)x&(2e-1)y-1&(2e-1)z\\\
(\epsilon+e-1)x&(\epsilon+e-1)y&(\epsilon+e-1)z-1\\\ \end{pmatrix},$ (11)

which has eigenvalues $\lambda_{1}=\lambda_{2}=-1$ and $\lambda_{3}=\epsilon
x+e(1-x)-1+\epsilon(1-y)+ey-1<0$. Therefore, $g^{*}$ is stable.

###  3.2 Private Assessment

For Shunning, the sole equilibrium frequency of good individuals is

$g^{*}=\frac{\epsilon g_{2}^{*}z+e(1-g_{2}^{*}z)}{1-(\epsilon-e)x}.$ (12)

The Jacobian of the system evaluated at this equilibrium is

$\mathbf{J}(g^{*})=\begin{pmatrix}(\epsilon-e)x-1&(\epsilon-e)y&(\epsilon-e)z&0&0&0\\\
0&-1&0&0&0&0\\\ 0&0&-1&(\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z\\\
((\epsilon-e)x+1)g_{x}^{*}&(\epsilon-e)g_{x}^{*}y&(\epsilon-e)g_{x}^{*}z&-1&0&0\\\
0&e&0&0&-1&0\\\
0&0&g_{z}^{*}&(\epsilon-e)g_{z}^{*}x&(\epsilon-e)g_{z}^{*}y&(\epsilon-e)g_{z}^{*}z-1\\\
\end{pmatrix}.$ (13)

The characteristic equation is
$(1+\lambda)^{3}(\lambda^{3}+c_{2}\lambda^{2}+c_{1}\lambda+c_{0})=0$ with the
following coefficients:

$\displaystyle c_{2}$ $\displaystyle=3-(\epsilon-e)(x+g_{z}^{*}z)>2,$ (14a)
$\displaystyle c_{1}$
$\displaystyle=3-(\epsilon-e)(3g_{z}^{*}z+(2+(\epsilon-e)(g_{x}^{*}-g_{z}^{*})z)x)>0,$
(14b) $\displaystyle c_{0}$
$\displaystyle=1-(\epsilon-e)(x+2g_{z}^{*}z+2(\epsilon-e)(g_{x}^{*}-g_{z}^{*})xz)$
$\displaystyle=1-(\epsilon-e)(2ez+x(1+2g^{*}z(\epsilon-e)^{2}))-2z(\epsilon-e)^{2}(1-(\epsilon-e)x)g_{2}^{*}$
$\displaystyle\geq
1-(\epsilon-e)(2ez+x(1+2g^{*}z(\epsilon-e)^{2}))-2z(\epsilon-e)^{2}(1-(\epsilon-e)x)g^{*}$
$\displaystyle=1-(\epsilon-e)x-2(\epsilon-e)((\epsilon-e)g^{*}+e)z$
$\displaystyle\geq 1-(\epsilon-e)x-\frac{2e(\epsilon-e)}{1-\epsilon+e}z$
$\displaystyle>1-(\epsilon-e)x-z\geq 0.$ (14c)

The inequality for $c_{0}$ follows for the following reasons:
$g_{x}^{*}=(\epsilon-e)g^{*}+e$ and $g_{z}^{*}=(\epsilon-e)g_{2}^{*}+e$;
$g^{*}\geq g_{2}^{*}$;
$g_{x}^{*}=(\epsilon-e)g^{*}+e\leq(\epsilon-e)g_{x}^{*}+e\implies
g_{x}^{*}\leq e/(1-\epsilon+e)$; and
$1-\epsilon+e-2e(\epsilon-e)=e_{1}+4(1-e_{1})e^{2}>0$. The first three
eigenvalues are negative as can be seen from the first factor of the
characteristic equation. The second factor is a cubic equation of $\lambda$.
Note that all of the coefficients of this cubic are positive. The Routh-
Hurwitz criterion for stability requires that all coefficients of this cubic
to be positive and $c_{2}c_{1}-c_{0}>0$. Checking this last condition gives us

$c_{2}c_{1}-c_{0}>2c_{1}-c_{0}=5-(\epsilon-e)(3x+4g_{z}^{*}z)>0.$ (15)

Therefore, $g^{*}$ is stable.

There are two equilibria for Staying under private assessment. The first of
which is $g^{*}=0$, and evaluating the Jacobian at this equilibrium gives us

$\mathbf{J}(0)=\begin{pmatrix}x\epsilon&y\epsilon&z\epsilon&0&0&0\\\
ex&ey&ez&0&0&0\\\ ex&ey&ez&(\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z\\\
0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ \end{pmatrix}.$ (16)

The eigenvalues are $\lambda_{i}=0$ for $i=1\ldots,5$ and
$\lambda_{6}=\epsilon x+e(1-x)>0$. Thus, $g^{*}=0$ is unstable. At the other
equilibrium, $g_{x}^{*}=\epsilon$, $g_{y}^{*}=e$,
$g_{z}^{*}=(\epsilon-e)g_{2}^{*}/g^{*}+e$, and the Jacobian evaluated at it is

$\displaystyle\mathbf{J}(g^{*})$
$\displaystyle=\begin{pmatrix}\mathbf{J}_{1}&\mathbf{J}_{2}\\\
\mathbf{J}_{3}&\mathbf{J}_{4}\end{pmatrix},$ (17a)
$\displaystyle\mathbf{J}_{1}$ $\displaystyle=\begin{pmatrix}-g^{*}&0&0\\\
0&-g^{*}&0\\\ (e-g_{z}^{*})x&(e-g_{z}^{*})y&(e-g_{z}^{*})z-g^{*}\\\
\end{pmatrix},$ (17b) $\displaystyle\mathbf{J}_{2}$
$\displaystyle=\begin{pmatrix}0&0&0\\\ 0&0&0\\\
(\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z\\\ \end{pmatrix},$ (17c)
$\displaystyle\mathbf{J}_{3}$ $\displaystyle=\begin{pmatrix}\epsilon
g^{*}&0&0\\\ 0&eg^{*}&0\\\
(e-g_{z}^{*})g_{z}^{*}x&(e-g_{z}^{*})g_{z}^{*}y&(e-g_{z}^{*})g_{z}^{*}z+g_{z}^{*}g^{*}\\\
\end{pmatrix},$ (17d) $\displaystyle\mathbf{J}_{4}$
$\displaystyle=\begin{pmatrix}-g^{*}&0&0\\\ 0&-g^{*}&0\\\
(\epsilon-e)g_{z}^{*}x&(\epsilon-e)g_{z}^{*}y&(\epsilon-e)g_{z}^{*}z-g^{*}\\\
\end{pmatrix}.$ (17e)

The characteristic equation is
$(\lambda+g^{*})^{4}(\lambda^{2}+c_{1}\lambda+c_{0})=0$. Since $g^{*}\geq
g_{y}^{*}=e$,

$\displaystyle c_{1}$ $\displaystyle=2g^{*}-ez+(1-\epsilon+e)g_{z}^{*}z\geq
e(2-z)+(1-\epsilon+e)g_{z}^{*}z>0,$ (18a) $\displaystyle c_{0}$
$\displaystyle=g^{*}(g^{*}+((1-2(\epsilon-e))g_{z}^{*}-e)z)\geq
g^{*}(g_{z}^{*}z+((1-2(\epsilon-e))g_{z}^{*}-e)z)=g^{*}\sqrt{k_{1}+k_{2}+k_{3}}>0,$
(18b) $\displaystyle k_{1}$ $\displaystyle=k1=e^{2}(y-z)^{2}+2\epsilon
exy+\epsilon^{2}x^{2}>0,$ (18c) $\displaystyle k_{2}$
$\displaystyle=2e^{2}yz(2(1-\epsilon^{2})+2e(2\epsilon-e))>0,$ (18d)
$\displaystyle k_{3}$ $\displaystyle=2\epsilon
exz+4\epsilon(1-\epsilon)(\epsilon-e)^{2}xz>0.$ (18e)

We obtain the inequality for Equation 18b by solving $g^{*}=\epsilon
x+ey+g_{z}^{*}z$ and
$g_{2}^{*}=\epsilon^{2}x+e^{2}y+(g_{z}^{*})^{2}z=\epsilon^{2}x+e^{2}y+((\epsilon-e)g_{2}^{*}/g^{*}+e)^{2}z$
for $g^{*}$ and $g_{2}^{*}$ and then plugging these solutions into $c_{0}$.
Note also that the radicand is positive. Thus, the last two eigenvalues must
be negative and so $g^{*}$ is stable.

Next consider Simple Standing. The equilibrium frequency of good individuals
is

$g^{*}=\frac{1-e+(\epsilon-e)zg_{2}^{*}}{1-2e+1-(\epsilon-e)},$ (19)

and the Jacobian evaluated at it is

$\displaystyle\mathbf{J}(g^{*})$
$\displaystyle=\begin{pmatrix}\mathbf{J}_{1}&\mathbf{J}_{2}\\\
\mathbf{J}_{3}&\mathbf{J}_{4}\end{pmatrix},$ (20a)
$\displaystyle\mathbf{J}_{1}$
$\displaystyle=\begin{pmatrix}(\epsilon+e-1)x-1&(\epsilon+e-1)y&(\epsilon+e-1)z\\\
(2e-1)x&(2e-1)y-1&(2e-1)z\\\ (2e-1)x&(2e-1)y&(2e-1)z-1\\\ \end{pmatrix},$
(20b) $\displaystyle\mathbf{J}_{2}$ $\displaystyle=\begin{pmatrix}0&0&0\\\
0&0&0\\\ (\epsilon-e)x&(\epsilon-e)y&(\epsilon-e)z\\\ \end{pmatrix},$ (20c)
$\displaystyle\mathbf{J}_{3}$
$\displaystyle=\begin{pmatrix}(\epsilon+e-1)g_{x}^{*}x+g_{x}^{*}&(\epsilon+e-1)g_{x}^{*}y&(\epsilon+e-1)g_{x}^{*}z\\\
(2e-1)g_{y}^{*}x&(2e-1)g_{y}^{*}y+g_{y}^{*}&(2e-1)g_{y}^{*}z\\\
(2e-1)g_{z}^{*}x&(2e-1)g_{z}^{*}y&(2e-1)g_{z}^{*}z+g_{z}^{*}\\\
\end{pmatrix},$ (20d) $\displaystyle\mathbf{J}_{4}$
$\displaystyle=\begin{pmatrix}-1&0&0\\\ 0&-1&0\\\
(\epsilon-e)g_{z}^{*}x&(\epsilon-e)g_{z}^{*}y&(\epsilon-e)g_{z}^{*}z-1\\\
\end{pmatrix}.$ (20e)

The characteristic equation is
$(\lambda+1)^{3}(\lambda^{3}+c_{2}\lambda^{2}+c_{1}\lambda+c_{0})=0$ with
positive coefficients:

$\displaystyle c_{2}$
$\displaystyle=2+1-(\epsilon-e)g_{z}^{*}z+(1-\epsilon-e)x+(1-2e)y+(1-2e)z>2,$
(21a) $\displaystyle c_{1}$
$\displaystyle=(1+(1-\epsilon-e)(2+(\epsilon-e)(g_{x}^{*}-g_{z}^{*})z))x+2(1-2e)(1-(\epsilon-e)(g_{z}^{*}-g_{y}^{*})z)y$
$\displaystyle+3(1-(\epsilon-e)g_{z}^{*}z)+2(1-2e)z>0,$ (21b) $\displaystyle
c_{0}$
$\displaystyle=(1+(1-\epsilon-e)(1+2(\epsilon-e)(g_{x}^{*}-g_{z}^{*})z))x+2(e+(1-2e)(1-(\epsilon-e)(g_{z}^{*}-g_{y}^{*})z))y$
$\displaystyle+2(1-\epsilon g_{z}^{*}-e(1-g_{z}^{*}))z>0,$ (21c)

since $1-\epsilon-e=e_{1}(1-2e)>0$. The first three eigenvalues are negative.
Since all of the coefficients of the cubic are positive, we need only to
confirm that $c_{2}c_{1}-c_{0}>2c_{1}-c_{0}>0$ to prove stability. Checking
this last condition gives us

$\displaystyle 2c_{1}-c_{0}$
$\displaystyle=8-6e-3x(\epsilon-e)-4(\epsilon-e)(1-x-y)g_{z}^{*}$
$\displaystyle\geq 8-6e-3x(\epsilon-e)-4(\epsilon-e)(1-x-y)$
$\displaystyle=4-2e+4(1-\epsilon)+(\epsilon-e)(x+4y)>0.$ (22)

Therefore, it is stable.

Finally, consider Stern Judging, which has the equilibrium
$g^{*}=g_{x}^{*}=g_{y}^{*}=g_{z}^{*}=\tfrac{1}{2}$ [15]. Evaluating the
Jacobian at this equilibrium gives us

$\displaystyle\mathbf{J}(g^{*})$
$\displaystyle=\begin{pmatrix}\mathbf{J}_{1}&\mathbf{J}_{2}\\\
\mathbf{J}_{3}&\mathbf{J}_{4}\end{pmatrix},$ (23a)
$\displaystyle\mathbf{J}_{1}$
$\displaystyle=\begin{pmatrix}(2\epsilon-1)x-1&(2\epsilon-1)y&(2\epsilon-1)z\\\
(2e-1)x&(2e-1)y-1&(2e-1)z\\\
(2e-1+e-\epsilon)x&(2e-1+e-\epsilon)y&(2e-1+e-\epsilon)z-1\\\ \end{pmatrix},$
(23b) $\displaystyle\mathbf{J}_{2}$ $\displaystyle=\begin{pmatrix}0&0&0\\\
0&0&0\\\ 2(\epsilon-e)x&2(\epsilon-e)y&2(\epsilon-e)z\\\ \end{pmatrix},$ (23c)
$\displaystyle\mathbf{J}_{3}$
$\displaystyle=\begin{pmatrix}(2\epsilon-1)g_{x}^{*}x+g_{x}^{*}&(2\epsilon-1)g_{x}^{*}y&(2\epsilon-1)g_{x}^{*}z\\\
(2e-1)g_{y}^{*}x&(2e-1)g_{y}^{*}y+g_{y}^{*}&(2e-1)g_{y}^{*}z\\\
(2e-1+e-\epsilon)g_{z}^{*}x&(2e-1+e-\epsilon)g_{z}^{*}y&(2e-1+e-\epsilon)g_{z}^{*}z+g_{z}^{*}\\\
\end{pmatrix},$ (23d) $\displaystyle\mathbf{J}_{4}$
$\displaystyle=\begin{pmatrix}-1&0&0\\\ 0&-1&0\\\
2(\epsilon-e)g_{z}^{*}x&2(\epsilon-e)g_{z}^{*}y&2(\epsilon-e)g_{z}^{*}z-1\\\
\end{pmatrix}.$ (23e)

The characteristic equation is
$(\lambda+1)^{2}(\lambda^{4}+c_{3}\lambda^{3}+c_{2}\lambda^{2}+c_{1}\lambda+c_{0})=0$
with coefficients:

$\displaystyle c_{3}$ $\displaystyle=4-\epsilon
x+(1-\epsilon)x+(1-2e)(1-x)>0,$ (24a) $\displaystyle c_{2}$
$\displaystyle=3+3(1-\epsilon
x)+3(1-\epsilon)x+3(1-2e)y+(2(1-2e)+1-\epsilon-e)z>3,$ (24b) $\displaystyle
c_{1}$ $\displaystyle=3(1-\epsilon x)+3(1-\epsilon)x+3(1-2e)y+1-\epsilon
z+(2(1-2e)+1-\epsilon)z>0$ (24c) $\displaystyle c_{0}$
$\displaystyle=1-\epsilon x+(1-\epsilon)x+(1-2e)y+(1-\epsilon-e)z>0,$ (24d)

Further, we have the following inequalities:

$\displaystyle c_{3}c_{2}-c_{1}\geq 3c_{3}-c_{1}=8-2(\epsilon-e)z>0,$ (25a)
$\displaystyle c_{3}c_{2}c_{1}-c_{3}^{2}c_{0}-c_{1}^{2}=k_{1}k_{2}>0,$ (25b)
$\displaystyle k_{1}=2(2-(2\epsilon-1)x+(1-2e)(y+z))>0,$ (25c) $\displaystyle
k_{2}=(4+2(1-2\epsilon)x+2(1-2e)y+(1-2e+1-\epsilon-e)z))^{2}>0.$ (25d)

Therefore, $g^{*}$ is stable by the Routh-Hurwitz criteria.

##  4 Discussion

Indirect reciprocity is a key mechanism to promote cooperation and has been
well studied in the literature with both theoretical models and experiments.
Models have shown how indirect reciprocity can evolve and how it can promote
cooperation. Additionally, experimental evidence of indirect reciprocity has
been found in both humans and other animals [1, 10, 20, 21, 24]. Many of the
mathematical models of indirect reciprocity assume a fast dynamic for
reputations and a slow dynamic for strategies. That is to say, reputations of
individuals are assessed and reach an equilibrium relatively quickly. Expected
payoffs are calculated given these reputations. Then, individuals can change
their strategies by imitating those who have greater payoffs. Reputations
converge to an equilibrium quickly again, and so on. These models assume that
reputations converge to a unique equilibrium, but this was not proven for
either public or private assessment of reputations. Here, we closed this gap,
and have shown that the reputational dynamics that occur rapidly do converge
to unique equilibria for each of the five standard norms and two assessment
rules, which provides a basis for the previous analysis of the strategical
dynamics in the literature.

Extensions to the models may be qualitatively different than the reputational
dynamics explored here. For example, the norms we considered are zeroth order
(Scoring) and first order (Shunning, Staying, Simple Standing, and Stern
Judging). Assignment of reputations under Scoring only depends upon the action
of the donor while assignments of the other norms also depends on the
reputation of the recipient. Higher order norms — those that use other
information such as the previous reputation of the donor or multiple
observations of the donor — may not lead to convergence to a unique set of
reputations. For third order norms, the reputational system can be bistable,
and when observers make multiple observations, reputations may not converge
(unpublished research). We note that that our systems of ODEs contain at most
cubic polynomials with respect to the variables. The case of multiple
observations is quartic, while the abductive reasoning model — which has
conditional convergence — involves rational functions [16]. Finding higher
order norms that are relevant to behaviour and that do not converge to
reputational equilibria is an area for future research. Another research area
that may lead to non-convergence is finite populations whether well-mixed or
on a network. It’s possible that small populations do not converge to unique
equilibria or that there are network configurations that also impede
convergence.

### Code and data availability

Code to verify analytical results is available at
github.com/bmorsky/indirectReciprocity-convergence.

## References

  * [1] Çağlar Akçay, Veronica A Reed, S Elizabeth Campbell, Christopher N Templeton, and Michael D Beecher.  Indirect reciprocity: song sparrows distrust aggressive neighbours based on eavesdropping.  Animal Behaviour, 80(6):1041–1047, 2010.
  * [2] Hannelore Brandt and Karl Sigmund.  The logic of reprobation: assessment and action rules for indirect reciprocation.  Journal of theoretical biology, 231(4):475–486, 2004.
  * [3] Fabio ACC Chalub, Francisco C Santos, and Jorge M Pacheco.  The evolution of norms.  Journal of theoretical biology, 241(2):233–240, 2006.
  * [4] Michael A Fishman.  Indirect reciprocity among imperfect individuals.  Journal of Theoretical Biology, 225(3):285–292, 2003.
  * [5] Christian Hilbe, Laura Schmid, Josef Tkadlec, Krishnendu Chatterjee, and Martin A Nowak.  Indirect reciprocity with private, noisy, and incomplete information.  Proceedings of the national academy of sciences, 115(48):12241–12246, 2018.
  * [6] Olof Leimar and Peter Hammerstein.  Evolution of cooperation through indirect reciprocity.  Proceedings of the Royal Society of London. Series B: Biological Sciences, 268(1468):745–753, 2001.
  * [7] Manfred Milinski, Dirk Semmann, Theo CM Bakker, and Hans-Jürgen Krambeck.  Cooperation through indirect reciprocity: image scoring or standing strategy?  Proceedings of the Royal Society of London. Series B: Biological Sciences, 268(1484):2495–2501, 2001.
  * [8] Bryce Morsky, Joshua B Plotkin, and Erol Akcay.  Indirect reciprocity with bayesian reasoning and biases.  SocArXiv. October, 16, 2023.
  * [9] Yutaka Nakai and Masayoshi Muto.  Emergence and collapse of peace with friend selection strategies.  Journal of Artificial Societies and Social Simulation, 11(3):6, 2008\.
  * [10] Elena Nava, Emanuela Croci, and Chiara Turati.  ‘I see you sharing, thus I share with you’: indirect reciprocity in toddlers but not infants.  Palgrave Communications, 5(1):1–9, 2019.
  * [11] Martin A Nowak and Karl Sigmund.  Evolution of indirect reciprocity.  Nature, 437(7063):1291–1298, 2005.
  * [12] Hisashi Ohtsuki and Yoh Iwasa.  How should we define goodness?—reputation dynamics in indirect reciprocity.  Journal of theoretical biology, 231(1):107–120, 2004.
  * [13] Hisashi Ohtsuki and Yoh Iwasa.  The leading eight: social norms that can maintain cooperation by indirect reciprocity.  Journal of theoretical biology, 239(4):435–444, 2006.
  * [14] Isamu Okada.  A review of theoretical studies on indirect reciprocity.  Games, 11(3):27, 2020.
  * [15] Isamu Okada, Tatsuya Sasaki, and Yutaka Nakai.  A solution for private assessment in indirect reciprocity using solitary observation.  Journal of theoretical biology, 455:7–15, 2018.
  * [16] Neel Pandula, Erol Akçay, and Bryce Morsky.  Indirect reciprocity with abductive reasoning.  Journal of Theoretical Biology, 580:111715, 2024.
  * [17] Arunas L Radzvilavicius, Alexander J Stewart, and Joshua B Plotkin.  Evolution of empathetic moral evaluation.  eLife, 8:e44269, 2019.
  * [18] Fernando P Santos, Jorge M Pacheco, and Francisco C Santos.  Evolution of cooperation under indirect reciprocity and arbitrary exploration rates.  Scientific reports, 6(1):37517, 2016.
  * [19] Tatsuya Sasaki, Isamu Okada, and Yutaka Nakai.  The evolution of conditional moral assessment in indirect reciprocity.  Scientific reports, 7(1):1–8, 2017.
  * [20] Ingrid Seinen and Arthur Schram.  Social status and group norms: Indirect reciprocity in a repeated helping experiment.  European economic review, 50(3):581–602, 2006.
  * [21] Ralf D Sommerfeld, Hans-Jürgen Krambeck, Dirk Semmann, and Manfred Milinski.  Gossip as an alternative for direct observation in games of indirect reciprocity.  Proceedings of the national academy of sciences, 104(44):17435–17440, 2007.
  * [22] Nobuyuki Takahashi and Rie Mashima.  The importance of subjectivity in perceptual errors on the emergence of indirect reciprocity.  Journal of Theoretical Biology, 243(3):418–436, 2006.
  * [23] Claus Wedekind and Manfred Milinski.  Cooperation through image scoring in humans.  Science, 288(5467):850–852, 2000.
  * [24] Erez Yoeli, Moshe Hoffman, David G Rand, and Martin A Nowak.  Powering up with indirect reciprocity in a large-scale field experiment.  Proceedings of the National Academy of Sciences, 110(Supplement 2):10424–10429, 2013.


# New results on sparse representations in unions of orthonormal bases

Tao Zhang and Gennian Ge The research of G. Ge was supported by the National
Key Research and Development Program of China under Grant 2020YFA0712100, the
National Natural Science Foundation of China under Grant 12231014, and Beijing
Scholars Program.T. Zhang is with the Institute of Mathematics and
Interdisciplinary Sciences, Xidian University, Xi’an 710071, China (e-mail:
zhant220@163.com).G. Ge is with the School of Mathematics Sciences, Capital
Normal University, Beijing 100048, China (e-mail: gnge@zju.edu.cn).

###### Abstract

The problem of sparse representation has significant applications in signal
processing. The spark of a dictionary plays a crucial role in the study of
sparse representation. Donoho and Elad initially explored the spark, and they
provided a general lower bound. When the dictionary is a union of several
orthonormal bases, Gribonval and Nielsen presented an improved lower bound for
spark. In this paper, we introduce a new construction of dictionary, achieving
the spark bound given by Gribonval and Nielsen. Our result extends Shen et
al.’ s findings [IEEE Trans. Inform. Theory, vol. 68, pp. 4230–4243, 2022].

###### Index Terms:

Sparse representation, spark, mutual coherence, orthonormal bases.

##  I Introduction

Due to the applications in compressed sensing, researchers are interested in
sparse representation problems [1, 5, 6]. Given a real column vector
$v\in\mathbb{R}^{n}$, the goal is to find an efficient representation of the
signal $v$. Let $B=\\{b_{1},b_{2},\dots,b_{n}\\}$ be an orthonormal basis of
$\mathbb{R}^{n}$, then

$\displaystyle
v=\begin{pmatrix}b_{1}&b_{2}&\cdots&b_{n}\end{pmatrix}\begin{pmatrix}v_{1}\\\
v_{2}\\\ \vdots\\\ v_{n}\end{pmatrix}=\sum_{i=1}^{n}v_{i}b_{i},$

where $v_{i}=\langle v,b_{i}\rangle$. Now we consider a more general problem
where the orthonormal basis is replaced by a dictionary of $\mathbb{R}^{n}$.

######  Definition 1.1.

A dictionary of $\mathbb{R}^{n}$ is a family of $N\geq n$ unit column vectors
$\\{d_{i}:i=1,2,\dots,N\\}$ that spans $\mathbb{R}^{n}$. We will use the
matrix notation $D=[d_{1},d_{2},\dots,d_{N}]$ for a dictionary.

If $N>n$, then the representation of $v$ is not unique, i.e., there are many
solutions for the equation $Dx=v$. The goal of compressed sensing is to find
the sparest representation among them. Then it is natural to consider the
following optimization problem:

$\displaystyle\min_{x}\|x\|_{0}\text{ subject to }v=Dx.$ (1)

In general, problem (1) is NP hard [14]. Following [1, 2], the following two
concepts are important in the study of sparse representation.

######  Definition 1.2.

The mutual coherence $\mu(D)$ of a given matrix $D$ is the largest magnitude
of the inner product between two columns of $D$, i.e.,

$\mu(D)=\max_{i\neq j}|\langle d_{i},d_{j}\rangle|.$

######  Definition 1.3.

The spark $\eta(D)$ of a given matrix $D$ is the smallest number of columns
from $D$ that are linearly dependent, i.e.,

$\eta(D)=\min_{x\in\ker(D),x\neq 0}\|x\|_{0},$

where $\ker(D)$ is the null space of $D$.

In [2, 7], the authors proved that if the equation $v=Dx$ has a solution
$x_{0}$ satisfying $\|x_{0}\|_{0}<\frac{\eta(D)}{2}$, then $x_{0}$ is the
unique solution for problem (1). Hence it is interesting to consider
dictionary that supports the largest possible sparse vectors. The problem of
computing the spark of a matrix is NP hard [2, 18]. In [17], the author gave a
specialized algorithm to compute the spark. Dictionary with large spark also
has applications in linear sensor arrays [12] and tensor decompositions [10].

For any dictionary $D$, Donoho and Elad [2] proved that

$\eta(D)\geq 1+\frac{1}{\mu(D)}.$

If $D$ is a union of two orthonormal bases, then a better bound can be found
in [4]

$\displaystyle\eta(D)\geq\frac{2}{\mu(D)}.$

The above bound was generalized by Gribonval and Nielsen [9], they proved that
if $D$ is a union of $q+1$ orthonormal bases, then

$\displaystyle\eta(D)\geq(1+\frac{1}{q})\frac{1}{\mu(D)}.$ (2)

In the same paper, the authors asked whether there exist examples for which
the equality holds in (2) when $q>1$. In [15], the authors gave a positive
answer to above question. Moreover, they proved that for $q=2^{r}$, $r$ is a
positive integer, $t=1$ or 2, there exists a dictionary $D$ in
$\mathbb{R}^{q^{2t}}$, which is a union of $q+1$ orthonormal bases, such that
the spark of $D$ attains bound (2). Then it is natural to ask the following
problem.

######  Problem 1.

For which $n,d$, there exists a dictionary $D$ in $\mathbb{R}^{n}$, which is a
union of $d$ orthonormal bases, such that the spark of $D$ attains bound (2).

For the above problem, Shen et al. [15] settled the case $(n,d)=(q^{2t},q+1)$,
where $q=2^{r}$, $r$ is a positive integer and $t=1$ or 2. We also refer the
readers to [2, 3, 8, 9, 16] for more dictionaries that are unions of several
orthonormal bases.

In this paper, we solve Problem 1 for $(n,d)=(q^{2t},q+1)$, where $q=2^{r}$
and $t,r$ are any positive integers. More precisely, We prove that

######  Theorem 1.4.

Let $t,r$ be positive integers, $q=2^{r}$, then there exists a dictionary $D$
in $\mathbb{R}^{q^{2t}}$ which is a union of $q+1$ orthonormal bases
satisfying $\eta(D)=q^{t}+q^{t-1}$ and $\mu(D)=\frac{1}{q^{t}}$.

It is easy to see that the spark of dictionary in Theorem 1.4 attains bound
(2). This paper is organized as follows. In Section II, we recall some basics
of finite fields. In Section III, we prove the main theorem.

##  II Preliminaries

Let $m,n$ be integers with $m\mid n$. For any $a\in\mathbb{F}_{2^{n}}$, the
trace of $a$ from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{m}}$ is defined by

$\text{Tr}_{m}^{n}(a)=a+a^{2^{m}}+a^{2^{2m}}+\cdots+a^{2^{n-m}}.$

It is easy to see that $\text{Tr}_{m}^{n}(a)\in\mathbb{F}_{2^{m}}$. We recall
some properties of trace function.

######  Lemma 2.1.

[13, Theorem 2.1.83] Let $m,n$ be integers with $m\mid n$. Then the trace
function satisfies the following properties:

  1. 1.

$\text{Tr}_{m}^{n}(a+b)=\text{Tr}_{m}^{n}(a)+\text{Tr}_{m}^{n}(b)$ for all
$a,b\in\mathbb{F}_{2^{n}}$;

  2. 2.

$\text{Tr}_{m}^{n}(ca)=c\text{Tr}_{m}^{n}(a)$ for all $a\in\mathbb{F}_{2^{n}}$
and $c\in\mathbb{F}_{2^{m}}$;

  3. 3.

$\text{Tr}_{m}^{n}(a^{2^{m}})=\text{Tr}_{m}^{n}(a)$ for all
$a\in\mathbb{F}_{2^{n}}$;

  4. 4.

$|\\{x\in\mathbb{F}_{2^{n}}:\ \text{Tr}_{m}^{n}(x)=c\\}|=2^{n-m}$ for any
$c\in\mathbb{F}_{2^{m}}$.

######  Lemma 2.2.

[11, Theorem 2.26] Let $l,m,n$ be integers with $l\mid m\mid n$. Then
$\text{Tr}_{l}^{n}(a)=\text{Tr}_{l}^{m}(\text{Tr}_{m}^{n}(a))$ for all
$a\in\mathbb{F}_{2^{n}}$.

From Lemma 2.1, we have the following corollary.

######  Corollary 2.3.

$\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{n}(x)}=0$.

###### Proof.

Since $|\\{x\in\mathbb{F}_{2^{n}}:\
\text{Tr}_{1}^{n}(x)=0\\}|=|\\{x\in\mathbb{F}_{2^{n}}:\
\text{Tr}_{1}^{n}(x)=1\\}|=2^{n-1}$, then
$\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{n}(x)}=0$. ∎

We also need the following lemma.

######  Lemma 2.4.

[11, Corollary 3.79] For a positive integer $n$, the equation $x^{2}+ax+b=0$
with $a,b\in\mathbb{F}_{2^{n}}$, $a\neq 0$, has solutions in
$\mathbb{F}_{2^{n}}$ if and only if $\text{Tr}_{1}^{n}(\frac{b}{a^{2}})=0$.

##  III Proof of Theorem 1.4

Let $t,r$ be positive integers, $m=tr$ and $n=2m=2tr$. Let $q=2^{r}$. Define
$B_{q+1}=\\{e_{x}:x\in\mathbb{F}_{2^{n}}\\}$, and

$B_{a}=\\{B_{a,b}=\frac{1}{2^{m}}((-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(bx)})_{x\in\mathbb{F}_{2^{n}}}:b\in\mathbb{F}_{2^{n}}\\},$

for $a\in\mathbb{F}_{2^{r}}$. We first prove that the vectors in $B_{a}$ form
an orthonormal basis of $R^{2^{n}}$.

######  Lemma 3.1.

For each $a\in\mathbb{F}_{2^{r}}$, $B_{a}$ is an orthonormal basis of
$R^{2^{n}}$.

###### Proof.

For any $b_{1},b_{2}\in\mathbb{F}_{2^{n}}$ with $b_{1}\neq b_{2}$, we have

$\displaystyle\langle B_{a,b_{1}},B_{a,b_{2}}\rangle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(b_{1}x)}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(b_{2}x)}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{n}((b_{1}+b_{2})x)}$
$\displaystyle=$ $\displaystyle 0,$

where the last equality follows from $b_{1}+b_{2}\neq 0$,
$\\{(b_{1}+b_{2})x:x\in\mathbb{F}_{2^{n}}\\}=\\{x:x\in\mathbb{F}_{2^{n}}\\}$
and Corollary 2.3. Note that $|B_{a}|=2^{n}$, then $B_{a}$ is an orthogonal
basis of $R^{2^{n}}$. ∎

For any $a\in\mathbb{F}_{2^{n}}$, define $\overline{a}:=a^{2^{m}}$. The unit
circle of $\mathbb{F}_{2^{n}}$ is the set

$U=\\{u\in\mathbb{F}_{2^{n}}:u^{2^{m}+1}=u\overline{u}=1\\}.$

Note that $\gcd(2^{m}+1,2^{m}-1)=1$, then for any
$a\in\mathbb{F}_{2^{n}}^{*}$, there exists a unique representation $a=uv$,
where $u\in U$ and $v\in\mathbb{F}_{2^{m}}^{*}$. Now we consider the inner
product between vectors from $B_{a_{1}}$ and $B_{a_{2}}$, where $a_{1}\neq
a_{2}$.

######  Lemma 3.2.

For any $a_{1},a_{2}\in\mathbb{F}_{2^{r}}$ with $a_{1}\neq a_{2}$, and
$b_{1},b_{2}\in\mathbb{F}_{2^{n}}$, we have $|\langle
B_{a_{1},b_{1}},B_{a_{2},b_{2}}\rangle|=\frac{1}{2^{m}}$.

###### Proof.

$\displaystyle\langle B_{a_{1},b_{1}},B_{a_{2},b_{2}}\rangle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}(a_{1}x^{2^{m}+1})+\text{Tr}_{1}^{n}(b_{1}x)}(-1)^{\text{Tr}_{1}^{m}(a_{2}x^{2^{m}+1})+\text{Tr}_{1}^{n}(b_{2}x)}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}((a_{1}+a_{2})x^{2^{m}+1})+\text{Tr}_{1}^{n}((b_{1}+b_{2})x)}.$

Set $a=a_{1}+a_{2}$, $b=b_{1}+b_{2}$, then $a\neq 0$ and

$\displaystyle\langle B_{a_{1},b_{1}},B_{a_{2},b_{2}}\rangle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(bx)}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1}+bx+(bx)^{2^{m}})}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2^{n}}}(-1)^{\text{Tr}_{1}^{m}(ax\overline{x}+bx+\overline{bx})}$
$\displaystyle=$ $\displaystyle\frac{1}{2^{n}}(1+\sum_{u\in
U}\sum_{v\in\mathbb{F}_{2^{m}}^{*}}(-1)^{\text{Tr}_{1}^{m}(auv\overline{uv}+buv+\overline{buv})})$
$\displaystyle=$ $\displaystyle\frac{1}{2^{n}}(1+\sum_{u\in
U}\sum_{v\in\mathbb{F}_{2^{m}}^{*}}(-1)^{\text{Tr}_{1}^{m}(av^{2}+buv+\overline{bu}v)})$
$\displaystyle=$ $\displaystyle\frac{1}{2^{n}}(1+\sum_{u\in
U}\sum_{v\in\mathbb{F}_{2^{m}}^{*}}(-1)^{\text{Tr}_{1}^{m}((a^{\prime}+bu+\overline{bu})v)}),$

where $a^{\prime}=a^{2^{m-1}}$. Let $b=b_{1}b_{2}$, where $b_{1}\in U$ and
$b_{2}\in\mathbb{F}_{2^{m}}^{*}$, then
$a^{\prime}+bu+\overline{bu}=a^{\prime}+b_{2}(b_{1}u+\overline{b_{1}u})$. Let

$N=|\\{x\in U:a^{\prime}+b_{2}(x+\overline{x})=0\\}|.$

If $u\in U$ is a solution for equation $a^{\prime}+b_{2}(x+\overline{x})=0$,
then $a^{\prime}+b_{2}(u+\overline{u})=0$. We have
$a^{\prime}u+b_{2}(u^{2}+1)=0$, i.e., $b_{2}u^{2}+a^{\prime}u+b_{2}=0$. Hence
$N\leq 2$. On the other hand, if $u\in U$ is a solution for equation
$a^{\prime}+b_{2}(x+\overline{x})=0$, then $\overline{u}\in U$ is also a
solution for equation $a^{\prime}+b_{2}(x+\overline{x})=0$. If
$u=\overline{u}$, then $u^{2}=u\overline{u}=1$. Thus $u=1$, this leads to
$a^{\prime}=0$, which is a contradiction. Therefore $N=0$ or 2. Then we have

$\langle
B_{a_{1},b_{1}},B_{a_{2},b_{2}}\rangle=\begin{cases}-\frac{1}{2^{m}},&\textup{
if }N=0;\\\ \frac{1}{2^{m}},&\textup{ if }N=2.\end{cases}$

This finishes the proof. ∎

The inner product between vectors from $B_{a}$ and $B_{q+1}$ is easy to get.

######  Lemma 3.3.

For any $a\in\mathbb{F}_{2^{r}}$, $b,x\in\mathbb{F}_{2^{n}}$, we have
$|\langle B_{a,b},e_{x}\rangle|=\frac{1}{2^{m}}$.

###### Proof.

Since $\langle
B_{a,b},e_{x}\rangle=\frac{1}{2^{m}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(bx)}$,
then $|\langle B_{a,b},e_{x}\rangle|=\frac{1}{2^{m}}$. ∎

Now we consider the linear dependency of vectors in $B_{a}$ and $B_{q+1}$, we
first prove a lemma.

######  Lemma 3.4.

For any $y\in\mathbb{F}_{2^{m}}$, we have

$|\\{b\in\mathbb{F}_{2^{m}}:\text{Tr}_{1}^{m}(by)=0,\text{Tr}_{r}^{m}(b)=0\\}|=\begin{cases}2^{m-r-1},&\textup{
if }y\notin\mathbb{F}_{2^{r}};\\\ 2^{m-r},&\textup{ if
}y\in\mathbb{F}_{2^{r}}.\end{cases}$

###### Proof.

We can compute to get

$\displaystyle|\\{b\in\mathbb{F}_{2^{m}}:\text{Tr}_{1}^{m}(by)=0,\text{Tr}_{r}^{m}(b)=0\\}|$
$\displaystyle=$
$\displaystyle\frac{1}{2^{r+1}}\sum_{b\in\mathbb{F}_{2^{m}}}(1+(-1)^{\text{Tr}_{1}^{m}(by)})\sum_{\alpha\in\mathbb{F}_{2^{r}}}(-1)^{\text{Tr}_{1}^{r}(\alpha\text{Tr}_{r}^{m}(b))}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{r+1}}\sum_{\alpha\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}}}(1+(-1)^{\text{Tr}_{1}^{m}(by)})(-1)^{\text{Tr}_{1}^{m}(\alpha
b)}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{r+1}}\sum_{\alpha\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}}}((-1)^{\text{Tr}_{1}^{m}(\alpha
b)}+(-1)^{\text{Tr}_{1}^{m}(\alpha b+by)})$ $\displaystyle=$ $\displaystyle
2^{m-r-1}+\frac{1}{2^{r+1}}\sum_{\alpha\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}}}((-1)^{\text{Tr}_{1}^{m}((\alpha+y)b)})$
$\displaystyle=$ $\displaystyle\begin{cases}2^{m-r-1},&\textup{ if
}y\notin\mathbb{F}_{2^{r}};\\\ 2^{m-r},&\textup{ if
}y\in\mathbb{F}_{2^{r}}.\end{cases}$

∎

Define

$S=\\{x\in\mathbb{F}_{2^{n}}:\
\text{Tr}_{r}^{m}(x^{2^{m}+1})=0,x+x^{2^{m}}\in\mathbb{F}_{2^{r}}\\}.$

Then we find that the following vectors are linearly dependent.

######  Lemma 3.5.

$\sum_{a\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}B_{a,b}-\sum_{x\in
S}e_{x}=0$.

###### Proof.

We can compute to get

$\displaystyle\sum_{a\in\mathbb{F}_{2^{r}}}(-1)^{Tr_{1}^{m}(ax^{2^{m}+1})}$
$\displaystyle=$
$\displaystyle\sum_{a\in\mathbb{F}_{2^{r}}}(-1)^{Tr_{1}^{r}(a\text{Tr}_{r}^{m}(x^{2^{m}+1}))}$
$\displaystyle=$ $\displaystyle\begin{cases}0,&\textup{ if
}\text{Tr}_{r}^{m}(x^{2^{m}+1})\neq 0;\\\ 2^{r},&\textup{ if
}\text{Tr}_{r}^{m}(x^{2^{m}+1})=0,\end{cases}$

and

$\displaystyle\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}(-1)^{\text{Tr}_{1}^{n}(bx)}$
$\displaystyle=$
$\displaystyle\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}(-1)^{\text{Tr}_{1}^{m}(b(x+x^{2^{m}}))}$
$\displaystyle=$ $\displaystyle\begin{cases}0,&\textup{ if
}x+x^{2^{m}}\notin\mathbb{F}_{2^{r}};\\\ 2^{m-r},&\textup{ if
}x+x^{2^{m}}\in\mathbb{F}_{2^{r}},\end{cases}$

where the last equation follows from Lemma 3.4. For a vector
$A\in\mathbb{F}_{2^{n}}^{2^{n}}$, we use $[A]_{x}$ to denote its $x$-th
coordinate. From above two equations, we have

$\displaystyle[\sum_{a\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}B_{a,b}]_{x}$
$\displaystyle=$
$\displaystyle\sum_{a\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}\frac{1}{2^{m}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})+\text{Tr}_{1}^{n}(bx)}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{m}}\sum_{a\in\mathbb{F}_{2^{r}}}(-1)^{\text{Tr}_{1}^{m}(ax^{2^{m}+1})}\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}(-1)^{\text{Tr}_{1}^{n}(bx)}$
$\displaystyle=$ $\displaystyle\begin{cases}0,&\textup{ if
}\text{Tr}_{r}^{m}(x^{2^{m}+1})\neq 0\text{ or
}x+x^{2^{m}}\notin\mathbb{F}_{2^{r}};\\\ 1,&\textup{ if
}\text{Tr}_{r}^{m}(x^{2^{m}+1})=0,x+x^{2^{m}}\in\mathbb{F}_{2^{r}},\end{cases}$
$\displaystyle=$ $\displaystyle\begin{cases}0,&\textup{ if }x\notin S;\\\
1,&\textup{ if }x\in S.\end{cases}$

Hence
$\sum_{a\in\mathbb{F}_{2^{r}}}\sum_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}B_{a,b}-\sum_{x\in
S}e_{x}=0$. ∎

Now we compute the size of $S$.

######  Lemma 3.6.

$|S|=2^{m-r}.$

###### Proof.

For any $x\in S$, let $A=x\overline{x}$ and $B=x+\overline{x}$. Then
$\text{Tr}_{r}^{m}(A)=0$ and $B\in\mathbb{F}_{2^{r}}$.

If $x\in\mathbb{F}_{2^{m}}$, then $B=x+\overline{x}=0\in\mathbb{F}_{2^{r}}$
and $0=\text{Tr}_{r}^{m}(A)=\text{Tr}_{r}^{m}(x^{2})=\text{Tr}_{r}^{m}(x)$. By
Lemma 2.1, there are $2^{m-r}$ such $x$.

If $x\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}$, then $x,\overline{x}$
are solutions of equation $X^{2}+BX+A=0$. Note that
$B,A\in\mathbb{F}_{2^{m}}$, by Lemma 2.4,
$x,\overline{x}\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}$ if and only
if $\text{Tr}_{1}^{m}(\frac{A}{B^{2}})=1$. On the other hand,
$\text{Tr}_{1}^{m}(\frac{A}{B^{2}})=\text{Tr}_{1}^{r}(\text{Tr}_{r}^{m}(\frac{A}{B^{2}}))=\text{Tr}_{1}^{r}(\frac{1}{B^{2}}\text{Tr}_{r}^{m}(A))=0$,
which is a contradiction. Therefore, $|S|=2^{m-r}.$ ∎

Proof of Theorem 1.4:  Let
$D=B_{q+1}\cup(\cup_{a\in\mathbb{F}_{2^{r}}}B_{a})$, then $D$ is a dictionary
in $\mathbb{R}^{q^{2t}}$. By Lemma 3.1, $D$ is a union of $2^{r}+1=q+1$
orthonormal bases. By Lemmas 3.2 and 3.3, we have
$\mu(D)=\frac{1}{2^{m}}=\frac{1}{q^{t}}$. From Lemma 3.5, the vectors in the
set

$(\cup_{a\in\mathbb{F}_{2^{r}}}\cup_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}B_{a,b})\cup(\cup_{x\in
S}e_{x})$

are linearly dependent. By Lemma 3.6, we can get

$\displaystyle|(\cup_{a\in\mathbb{F}_{2^{r}}}\cup_{b\in\mathbb{F}_{2^{m}},\text{Tr}_{r}^{m}(b)=0}B_{a,b})\cup(\cup_{x\in
S}e_{x})|=$ $\displaystyle 2^{r}\cdot 2^{m-r}+2^{m-r}$ $\displaystyle=$
$\displaystyle 2^{m}+2^{m-r}$ $\displaystyle=$ $\displaystyle q^{t}+q^{t-1}.$

Hence $\eta(D)=q^{t}+q^{t-1}$. This finishes the proof.

## References

  * [1] A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,” _SIAM Rev._ , vol. 51, no. 1, pp. 34–81, 2009. [Online]. Available: https://doi.org/10.1137/060657704
  * [2] D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via $l^{1}$ minimization,” _Proc. Natl. Acad. Sci. USA_ , vol. 100, no. 5, pp. 2197–2202, 2003. [Online]. Available: https://doi.org/10.1073/pnas.0437847100
  * [3] D. L. Donoho and X. Huo, “Uncertainty principles and ideal atomic decomposition,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 7, pp. 2845–2862, 2001. [Online]. Available: https://doi.org/10.1109/18.959265
  * [4] M. Elad and A. M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of bases,” _IEEE Trans. Inform. Theory_ , vol. 48, no. 9, pp. 2558–2567, 2002. [Online]. Available: https://doi.org/10.1109/TIT.2002.801410
  * [5] Y. Eldar and G. Kutyniok, _Compressed Sensing: Theory and Applications_. Cambridge, U.K.: Cambridge Univ. Press, 2012.
  * [6] S. Foucart and H. Rauhut, _A mathematical introduction to compressive sensing_ , ser. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013. [Online]. Available: https://doi.org/10.1007/978-0-8176-4948-7
  * [7] I. Gorodnitsky and B. Rao, “Sparse signal reconstruction from limited data using focuss: a re-weighted minimum norm algorithm,” _IEEE Transactions on Signal Processing_ , vol. 45, no. 3, pp. 600–616, 1997.
  * [8] R. Gribonval and M. Nielsen, “Highly sparse representations from dictionaries are unique and independent of the sparseness measure,” _Appl. Comput. Harmon. Anal._ , vol. 22, no. 3, pp. 335–355, 2007. [Online]. Available: https://doi.org/10.1016/j.acha.2006.09.003
  * [9] ——, “Sparse representations in unions of bases,” _IEEE Trans. Inform. Theory_ , vol. 49, no. 12, pp. 3320–3325, 2003. [Online]. Available: https://doi.org/10.1109/TIT.2003.820031
  * [10] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,” _SIAM Rev._ , vol. 51, no. 3, pp. 455–500, 2009. [Online]. Available: https://doi.org/10.1137/07070111X
  * [11] R. Lidl and H. Niederreiter, _Finite fields_ , 2nd ed., ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1997, vol. 20, with a foreword by P. M. Cohn.
  * [12] A. Manikas and C. Proukakis, “Modeling and estimation of ambiguities in linear arrays,” _IEEE Transactions on Signal Processing_ , vol. 46, no. 8, pp. 2166–2179, 1998.
  * [13] G. L. Mullen, Ed., _Handbook of finite fields_ , ser. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2013. [Online]. Available: https://doi.org/10.1201/b15006
  * [14] B. K. Natarajan, “Sparse approximate solutions to linear systems,” _SIAM J. Comput._ , vol. 24, no. 2, pp. 227–234, 1995. [Online]. Available: https://doi.org/10.1137/S0097539792240406
  * [15] Y. Shen, C. Yu, Y. Shen, and S. Li, “An open problem on sparse representations in unions of bases,” _IEEE Trans. Inform. Theory_ , vol. 68, no. 7, pp. 4230–4243, 2022.
  * [16] ——, “On sparse recovery algorithms in unions of orthonormal bases,” _J. Approx. Theory_ , vol. 289, pp. Paper No. 105 886, 15, 2023. [Online]. Available: https://doi.org/10.1016/j.jat.2023.105886
  * [17] A. M. Tillmann, “Computing the spark: mixed-integer programming for the (vector) matroid girth problem,” _Comput. Optim. Appl._ , vol. 74, no. 2, pp. 387–441, 2019. [Online]. Available: https://doi.org/10.1007/s10589-019-00114-9
  * [18] A. M. Tillmann and M. E. Pfetsch, “The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing,” _IEEE Trans. Inform. Theory_ , vol. 60, no. 2, pp. 1248–1259, 2014. [Online]. Available: https://doi.org/10.1109/TIT.2013.2290112