# The Activity of Black Hole Imprints on the Internal Plateau and the
Subsequent Sharp Decay

Tian-Ci Zheng Key Laboratory of Dark Matter and Space Astronomy, Purple
Mountain Observatory, Chinese Academy of Sciences, Nanjing 210034, China
School of Astronomy and Space Science, University of Science and Technology of
China, Hefei 230026, China  Da-Ming Wei Key Laboratory of Dark Matter and
Space Astronomy, Purple Mountain Observatory, Chinese Academy of Sciences,
Nanjing 210034, China  School of Astronomy and Space Science, University of
Science and Technology of China, Hefei 230026, China  Yun Wang Key Laboratory
of Dark Matter and Space Astronomy, Purple Mountain Observatory, Chinese
Academy of Sciences, Nanjing 210034, China  Hao Zhou Key Laboratory of Dark
Matter and Space Astronomy, Purple Mountain Observatory, Chinese Academy of
Sciences, Nanjing 210034, China  School of Astronomy and Space Science,
University of Science and Technology of China, Hefei 230026, China  Long Li
School of Astronomy and Space Science, University of Science and Technology of
China, Hefei 230026, China  Deep Space Exploration Laboratory/Department of
Astronomy, University of Science and Technology of China, Hefei 230026, China

###### Abstract

A stellar-mass black hole (BH) or a millisecond magnetar is believed to be
born as the central engine of Gamma-ray bursts (GRBs). The presence of
plateaus in the X-ray extended emission or afterglow of GRBs is widely
accepted as an indicator of magnetar central engine, particularly those with a
sharp decay (faster than $t^{-3}$), so-called internal plateau. However, an
alternative model, by taking the evolution of the magnetic flux at the BH
horizon into account, suggests that an internal plateau can also arise from a
Blandford-Znajek (BZ) mechanism powered jet (hereafter referred to as the BZ
jet). In this study, we propose that a precessional BZ jet would manifest a
Quasi-Periodic Oscillation (QPO) signature on the internal plateau and the
subsequent sharp decay. Such lightcurves cannot be readily explained by the
activity of a short-lived, supermassive magnetar, thus favoring a Kerr BH as
the central engine. The X-ray afterglow of GRB 050904, comprising nine flares,
is characterized by a QPO-modulated plateau and sharp decay, which can be well
reproduced by a precessional BZ jet model. Therefore, one potential clue for
distinguishing between these two engines lies in whether QPO signature
throughout the entire plateau and the subsequent sharp decay, as the magnetar
scenario suggests a collapse at the end of the plateau.

Gamma-ray bursts (629), Black hole physics(159), Stellar accretion
disks(1579), Relativistic jets(1390)

††software: emcee (Foreman-Mackey et al., 2013), REDFIT (Schulz & Mudelsee,
2002), GLS (Zechmeister & Kürster, 2009), WWZ (Aydin, 2017)

##  1 Introduction

Gamma-ray bursts (GRBs), known as the most energetic phenomena, release energy
equivalent to the total energy of a Sun in a mere few seconds, leaving behind
a mass of mist for scientists. There are two types of central engines
suggested to be born during the burst of GRBs, one being a hyper-accreting
stellar mass black hole (BH) (e.g., Popham et al., 1999) and the other being a
rapidly rotating and highly magnetized neutron star (so-called magnetar; e.g.,
Usov, 1992). Unfortunately, the erratic prompt emission provides scant
information for identifying the type of central engine. However, the
discoveries of X-ray (Costa et al., 1997) and optical (van Paradijs et al.,
1997) afterglows offer a promising means to explore the properties of the
central engine. The canonical X-ray afterglow lightcurve (Zhang et al., 2006;
Nousek et al., 2006) suggests that both X-ray plateaus and X-ray flares are
associated with a long-lasting central engine.

A shallow decay (or plateau) followed by a normal decay is widely observed in
GRB X-ray afterglows, and can be well interpreted by continuous energy
injection (Dai & Lu, 1998; Zhang et al., 2006; Nousek et al., 2006), geometric
effect (e.g., off-set observation of a structured jet; Peng et al., 2005),
time-dependent microphysics (Ioka et al., 2006; Wei & Fan, 2007) or
environment-influenced fireball radiation (Dereli-Bégué et al., 2022), etc.
For a plateau followed by a rapid decay, with a decay index $\alpha\sim-2.0$,
the most popular model being energy injection or the internal dissipation of a
magnetar wind (Dai & Lu, 1998; Zhang & Mészáros, 2001). In some peculiar
cases, the plateau followed by a sharp decay $\alpha<-3.0$ (e.g., Troja et
al., 2007; Liang et al., 2007), dubbed “internal” plateau (Lyons et al.,
2010), where the break is associated with the disruption of the central
engine, e.g., the collapse of a supermassive millisecond magnetar (Lyons et
al., 2010; Rowlinson et al., 2010, 2013). By considering the evolution of the
magnetic flux at the BH horizon, an internal plateau can be also derived from
a Blandford-Znajek (BZ) mechanism (Blandford & Znajek, 1977) powered jet
(Kisaka & Ioka, 2015; Tchekhovskoy & Giannios, 2015) (hereafter referred to as
the BZ jet), though this is yet to be extensively discussed.

It has been suggested that X-ray flares and prompt emission may share a common
origin, with the former potentially being induced by the intermittent
accretion of a long-lasting central engine (King et al., 2005; Perna et al.,
2006). Zheng et al. (2021) establish a connection between X-ray flares and the
magnetar plateau, aiming to investigate the existence of a potential disk
surrounding the central magnetar, where the successive flares upon the
magnetar plateau were suggested to have periodicity. Quasi-Periodic
Oscillation (QPO) behavior is a general phenomenon in astrophysics, observed
in various systems such as active galactic nuclei (Lu, 1990), X-ray binary
system (Sarazin et al., 1980), and softer gamma-ray repeater (Li et al.,
2022), etc. Portegies Zwart et al. (1999) proposed that a Lense-Thirring
effect (Lense & Thirring, 1918) induced jet precession would leave a pattern
on GRB prompt emission. Additionally, Lei et al. (2007) conducted a
morphological study, while Li et al. (2023) initiated a study to explore the
corresponding manifests in sGRBs. Recently, some potential QPO signals have
been identified in both the prompt phase (Zhang et al., 2022; Xiao et al.,
2022; Wang et al., 2022; Zhang et al., 2023) and the afterglow phase (Suvorov
& Kokkotas, 2020; Zou et al., 2021; Zou & Liang, 2022). Therefore, a
lightcurve exhibiting QPO characteristics can serve as a valuable tool for
monitoring the activity of the central engine. In this study, we propose that
the precession of a BZ jet induced by the Lense-Thirring effect will imprint a
QPO signature on the internal plateau and the subsequent sharp decay. Such
lightcurves cannot be readily interpreted as the activities of a short-lived,
supermassive magnetar and instead suggest the presence of a Kerr BH as the
central engine. The model successfully reproduces a distinctive X-ray
lightcurve of GRB 050904, which consists of nine flares. This paper is
organized as follows. In §2, we demonstrate that, by taking into account the
evolution of the magnetic field and the Lense-Thirring effect, the BZ jet can
generate a lightcurve, which is characterized by a QPO signature printed on
the internal plateau and the subsequent sharp decay. The model is applied to
the peculiar case of GRB 050904 and presented in §3. In §4, we test the
periodicity of the observed lightcurve of GRB 050904. In §5 we give the
conclusions and the discussions. The $\Lambda$CDM cosmology parameters in a
flat universe $H_{0}=67.4~{}\rm{km\ s^{-1}\ Mpc^{-1}}$ and $\Omega_{M}=0.315$
(Planck Collaboration et al., 2020) are adopted in this study.

##  2 emission from a precessional BZ jet

Currently, two models are involved in interpreting the observed internal
plateau in the afterglow of GRBs. The first model involves an internal
dissipation wind originating from a supermassive magnetar, in which the break
of the plateau signifies an abrupt collapse of the magnetar. The second model
pertains to an internal dissipation jet powered by BZ mechanism (Tchekhovskoy
& Giannios, 2015; Kisaka & Ioka, 2015), where the break of the plateau
corresponds to the expansion of the magnetosphere. One distinguishing factor
between these two models is that the latter has a continuously active central
engine throughout the plateau and the subsequent sharp decay, and the QPO
signature can help to record this continuous activity.

###  2.1 jets powered by BHs

The dimensionless spin parameter of a Kerr BH with mass $M_{\rm BH}$ can be
expressed as $a={\rm c}J_{\rm BH}/{\rm G}M^{2}_{\rm BH}$, where $J_{\rm BH}$
is the angular momentum of the BH, c and G represent the speed of light and
the gravitational constant, respectively. The magnetic flux passing through
the event horizon of the BH is represented by $\Phi_{\rm BH}\sim\pi
r^{2}_{H}B_{H}$, where $r_{H}$ is the radius of the outer horizon given by
$r_{H}={\rm G}M_{\rm BH}(1+(1-a^{2})^{1/2})/c^{2}$, and $B_{H}$ represents the
magnetic field strength at the horizon. The power of the BZ jet is highly
dependent on the magnetic flux, that is (e.g., Blandford & Znajek, 1977;
Tchekhovskoy et al., 2011)

$\displaystyle L_{\rm BZ}\approx\frac{kf}{4\pi{\rm c}}~{}\Phi^{2}_{\rm
BH}~{}\Omega^{2}_{H},$ (1)

where $k\approx 0.05$, the angular frequency of BH horizon $\Omega_{H}=a{\rm
c}/2r_{H}$. For $a\sim 1$, one have $f=1$, $r_{H}\sim{\rm G}M_{\rm BH}/c^{2}$.
The scenario with $a\sim 1$ is utilized for all calculations conducted in this
study.

According to the BH no-hair theorem, the magnetic field inherited from the
progenitor is expected to naturally diffuse out of the BH, as the BH formed.
The mass accretion rate of the magnetically arrested disc (MAD), however, is
so high that the magnetic flux is squeezed at the BH horizon (Tchekhovskoy &
Giannios, 2015). The cross-section of the magnetosphere, which the magnetic
flux passes through, depends on the balance between the ram pressure of the
accretion flow $P_{f}$ and the pressure exerted by the magnetic field $P_{B}$.
In the scenario of magnetic flux conservation, the magnetic pressure is
expressed as

$\displaystyle P_{B}=\frac{B^{2}_{\rm
H,0}}{8\pi}\left(\frac{R}{r_{H}}\right)^{-4},$ (2)

where $B_{\rm H,0}$ is the characteristic magnetic field strength while the
magnetic field is squeezed at the BH horizon, one has $B_{H}=B_{\rm
H,0}\left(\frac{R}{r_{H}}\right)^{-2}$, for $R\geq r_{H}$. The ram pressure of
accretion flow is denoted as

$\displaystyle P_{f}=\frac{GM_{\rm BH}\dot{M}}{2\pi R^{3}v_{R}},$ (3)

where $v_{R}=\epsilon(GM_{\rm BH}/R)^{1/2}$ is the radial velocity, and
$\epsilon\sim 10^{-2}$ (e.g., Tchekhovskoy et al., 2011; Zamaninasab et al.,
2014). The mass accretion rate $\dot{M}$ increases with time in the early
phase ($t<t_{p}$) and decreases with time in the later phase ($t>t_{p}$),
where $t_{p}$ represents the characteristic transformation time scale of the
mass accretion rate. For the later phase (Chevalier, 1989)

$\displaystyle\dot{M}=\dot{M}_{p}\left(\frac{t-t_{0}}{t_{p}-t_{0}}\right)^{-5/3},$
(4)

where $t_{0}$ is the initial time of accretion, and $\dot{M}_{p}$ is the
characteristic mass accretion rate at $t_{p}$. As the mass accretion rate
$\dot{M}$ decreases and falls below a critical value of $\dot{M}\sim
10^{-4}~{}\rm M_{\odot}~{}s^{-1}$ (Tchekhovskoy & Giannios, 2015), the ram
pressure drops below the magnetic pressure level. Consequently, the
magnetosphere will move away from the BH horizon, leading to the diffusion of
a portion of the magnetic flux beyond the horizon. The magnetic flux passing
through the BH horizon decreases as the magnetosphere size ($R_{m}$) increases

$\displaystyle\Phi_{\rm BH}=\pi r^{2}_{H}B_{\rm
H,0}\left(\frac{r_{H}}{R_{m}}\right)^{2},$ (5)

where

$\displaystyle\frac{r_{H}}{R_{m}}=5.28\left(\frac{\epsilon}{10^{-2}}\right)^{-2/3}\left(\frac{B_{\rm
H,0}}{10^{15}~{}\rm G}\right)^{-4/3}\left(\frac{M_{\rm BH}}{3~{}{\rm
M_{\odot}}}\right)^{-4/3}\left(\frac{\dot{M}_{p}}{10^{-4}~{}{\rm M_{\odot}}\rm
s^{-1}}\right)^{2/3}\left(\frac{t-t_{0}}{t_{p}-t_{0}}\right)^{-10/9}.$ (6)

Therefore, the power of the BZ jet can be written as

$\displaystyle L_{\rm BZ}$ $\displaystyle\approx$ $\displaystyle 1.44\times
10^{52}\left(\frac{\epsilon}{10^{-2}}\right)^{-8/3}~{}\left(\frac{B_{\rm
H,0}}{10^{15}{\rm G}}\right)^{-10/3}~{}\left(\frac{M_{\rm BH}}{3~{}{\rm
M}_{\odot}}\right)^{-10/3}~{}\left(\frac{\dot{M}_{p}}{10^{-4}~{}{\rm
M}_{\odot}}\right)^{8/3}~{}\left(\frac{t-t_{0}}{t_{p}-t_{0}}\right)^{-40/9}~{}{\rm
erg~{}s^{-1}}.$ (7)

The characteristic timescale for the diffusion of the magnetic field out of
the horizon can be derived by balancing the ram pressure with the magnetic
pressure

$\displaystyle t_{b}$ $\displaystyle=$
$\displaystyle\frac{4.47}{t_{p}-t_{0}}\left(\frac{\epsilon}{10^{-2}}\right)^{-3/5}\left(\frac{B_{\rm
H,0}}{10^{15}~{}\rm G}\right)^{-6/5}\left(\frac{M_{\rm BH}}{3~{}{\rm
M_{\odot}}}\right)^{-6/5}\left(\frac{\dot{M}_{p}}{10^{-4}~{}{\rm M_{\odot}}\rm
s^{-1}}\right)^{3/5}~{}{\rm s}.$ (8)

Therefore, the time-evolving power acts as a plateau followed by a sharp decay

$L(t)\approx\left\\{\begin{array}[]{ll}L_{0},&\quad t\leq t_{b},\\\ L_{\rm
0}\left(\frac{t}{t_{b}}\right)^{-40/9},&\quad t>t_{b},\end{array}\right.$ (9)

where characteristic luminosity is expressed as $L_{0}=\frac{\pi{\rm
c}}{320}r^{2}_{H}B^{2}_{\rm H,0}$. A smooth-broken-power-law function is
employed to describe an observed internal plateau and subsequent sharp decay.

$\displaystyle L_{\rm EM}=2\eta_{\rm
BZ}L_{0}\left(\left(\frac{t}{t_{b}}\right)^{\alpha_{1}}+\left(\frac{t}{t_{b}}\right)^{\alpha_{2}}\right)^{-1},$
(10)

where $\alpha_{2}$ represents the decay slope post the break time, with a
typical value of 40/9, and the supplemented $\alpha_{1}$ corresponds to the
decay slope before the break time, which connects the evolution of the spin of
the BH and the radius of the outer horizon. The radiative efficiency of the BZ
jet is denoted by $\eta_{\rm BZ}$, with a typical value of approximately 0.1,
as adopted from previous studies (Kisaka & Ioka, 2015; Zhang et al., 2007)

###  2.2 Precession of BZ jet

GRBs are believed to originate from a collimated jet. An ultra-relativistic BZ
jet presents a promising possibility for yielding a beaming GRB, in the
context of a BH central engine. Portegies Zwart et al. (1999) has proposed
that the intrinsic variability in certain GRB lightcurves may arise from the
precession of a jet.

In the case of a Kerr BH, its strong angular momentum exerts a dragging effect
on the neighbor space. This effect induces the inclined orbit plane of a
particle to precess around the central BH, which is known as the Lense-
Thirring effect (Lense & Thirring, 1918). Moreover, the accretion disk
surrounding the Kerr BH is also influenced by this effect. As discussed in §
2.1, the MAD with a high mass accretion rate would squeeze the magnetic flux
on the BH horizon. Consequently, the precessing MAD compels the direction of
the BZ jet to deviate from the spin axis of the BH and to align with the axis
of MAD, as described by Portegies Zwart et al. (1999). Finally, the jet
exhibits the same precession period as the MAD. The precession angular
frequency of the inclined plane is expressed as (Lei et al., 2013; Wilkins,
1972)

$\displaystyle\Omega=\frac{2GJ_{\rm BH}}{{\rm c}^{2}r^{3}},$ (11)

where $r$ is the radius of the precession orbit, the precession period is
$P=2\pi/\Omega$.

###  2.3 Evolving lightcurve originates from a precessing Jet

Since the jet is precessing, the angle between the observer’s line of sight
$\vec{r}_{\rm obs}$ and the direction of jet $\vec{r}_{\rm jet}$ should evolve
with time, and it can be written as (Lei et al., 2007; Liu et al., 2010)

$\displaystyle{\rm cos}(\psi)$ $\displaystyle=$ $\displaystyle\vec{r}_{\rm
obs}\cdot\vec{r}_{\rm jet}$ (12) $\displaystyle=$ $\displaystyle{\rm
cos}(\theta_{\rm jet}){\rm cos}(\theta_{\rm obs})+{\rm sin}(\theta_{\rm
jet}){\rm sin}(\theta_{\rm obs}){\rm cos}(\phi_{\rm jet}-\phi_{\rm obs}),$

where the $\theta_{\rm jet}$ and $\theta_{\rm obs}$ are the angles from the
precession axis to the jet and to the observer, respectively. $\phi_{\rm
jet}=\phi_{\rm jet,0}+2\pi t/P$ is the phase of jet, where $\phi_{\rm jet,0}$
corresponds to the initial phases, the phases of the observer $\phi_{\rm obs}$
is a constant. By setting constant $C=\phi_{\rm jet,0}-\phi_{\rm obs}$, a
time-dependent $\psi$ is written as

$\displaystyle{\rm cos}(\psi(t))={\rm cos}(\theta_{\rm jet}){\rm
cos}(\theta_{\rm obs})+{\rm sin}(\theta_{\rm jet}){\rm sin}(\theta_{\rm
obs}){\rm cos}(2\pi t/P+C).$ (13)

Taking into account the Doppler effect, the observed flux of an off-axis
observer is written as $F(\psi)=D^{3}F_{\psi=0}$, and the Doppler factor
$D=(1-\beta)/(1-\beta{\rm cos}(\psi))$, $\beta=(1-1/\Gamma^{2})^{1/2}$, where
$\Gamma$ is the Lorentz factor. Finally, the emission observed from a
precessing BZ jet can be summarized into

$\displaystyle L_{\rm obs}=2\eta_{\rm
BZ}D^{3}L_{0}\left(\left(\frac{t}{t_{b}}\right)^{\alpha_{1}}+\left(\frac{t}{t_{b}}\right)^{\alpha_{2}}\right)^{-1}.$
(14)

##  3 potential signature of precessing BZ jet in X-ray flares of GRB 050904

The energetic gamma-ray burst known as GRB 050904 was detected by the
Swift/BAT instrument at 01:51:44 on September 4, 2005 (UT) (Cummings et al.,
2005, hereafter $T_{0}$). The duration of its prompt emission was measured to
be $T_{\rm 90}=225\pm 10$ seconds (Sakamoto et al., 2005). Swift/XRT
instrument started to observe its X-ray emission since $T_{0}$+161 seconds.
The X-ray lightcurve, as observed, exhibits a total of nine flares from the
end of the rapid decay phase (approximately 600 seconds) to 55,000 seconds,
and the contour line of the lightcurve is characteristic by a plateau followed
by a sharp decay (with a decay index of $\alpha\sim-6$) (Evans et al., 2009).
A speculative period for successive flares is approximately 5600 seconds. The
confirmation of GRB 050904 as the first GRB with a spectroscopic redshift
larger than 6 was provided by subsequent optical observations (z= 6.29; Kawai
et al., 2006). The isotropic X-ray luminosity of GRB 050904 is derived with
$L_{\rm iso,X}(t)=4\pi D^{2}_{L}f_{X}(t)k(z)$, where $D_{L}$ and $f_{X}(t)$
are the luminosity distance and the observed X-ray flux, respectively. The
cosmological $k$-correction factor has $k(z)=(1+z)^{\gamma-2}$ (Bloom et al.,
2001; Şaşmaz Muş et al., 2019), where the average photon index of GRB 050904
has $\gamma=1.8$111https://www.swift.ac.uk/index.php. The investigation of the
jet opening angle for GRB050904 has been conducted extensively in previous
studies (Tagliaferri et al., 2005; Wei et al., 2006; Frail et al., 2006; Gou
et al., 2007), suggesting a potential range of values from $3^{\circ}$ to
$15^{\circ}$. In this study, we adopt a moderate value of
$\theta_{j}=10^{\circ}$, which corresponds to a beaming factor $f_{b}=1-{\rm
cos}\theta_{j}=0.015$, assuming that the flares share the same jet opening
angle as the prompt phase. Considering a small Lorentz factor required in the
below analysis, the energy fraction into XRT windows $\eta_{\rm X}=0.1$ (Xiao
& Dai, 2019) is adopted to calculate the afterglow luminosity $L_{\rm
obs}=L_{\rm iso,X}\times f_{b}/\eta_{X}$. The resulting lightcurve is
presented in Figure 1. The observed flares are interpreted as a consequence of
a precessing jet. A numerical fitting process based on radiation from a
precessional BZ jet is carried out subsequently.

Figure 1: A demonstration for QPO lightcurve. The observed lightcurve is shown
in green scatter, while the lightcurve predicted by the precessional BH jet is
represented by the red dashed line.

Equation (14) demonstrates that the amplitude magnitude of the observed pulses
is directly influenced by three parameters: luminosity $L_{0}$, Lorentz factor
$\Gamma$, and angle $\psi$. While searching for the parameter distribution, we
fix certain parameters based on observations to resolve the degeneracy of the
above three parameters. The amplitude of pulses spans a range of two orders of
magnitude, as depicted in Figure 1, allowing us to build an equation like
below

$\displaystyle\left(\frac{1-\beta{\rm cos}(\psi_{\rm min})}{1-\beta{\rm
cos}(\psi_{\rm max})}\right)^{3}\approx\frac{1}{100},$ (15)

where $\beta<1$ requires that

$\displaystyle\frac{1-0.01^{1/3}}{{\rm cos}(\psi_{\rm min})-0.01^{1/3}{\rm
cos}(\psi_{\rm max})}<1.$ (16)

As the emission from a precessing jet can intermittently move in and out of
the observer’s line of sight, one expects that $\psi_{\rm min}=|\theta_{\rm
jet}-\theta_{\rm obs}|\leq\theta_{j}/2$ and $\psi_{\rm max}=\theta_{\rm
jet}+\theta_{\rm obs}>\theta_{j}/2$. In this scenario, a pseudocolor plot
(Figure 2) is constructed to visualize the range of $\theta_{\rm jet}$ and
$\theta_{\rm obs}$, where the color in the plot represents the corresponding
values of $\Gamma$. The plot is configured with $10<\Gamma<200$, but the
majority of values fall within the range of 10 to 40. The given pseudocolor
plot reveals a symmetrical distribution of $\theta_{\rm jet}$ and $\theta_{\rm
obs}$, with a viable range spanning from 0.02 rad to 0.18 rad.

Figure 2:  The pseudocolor plot illustrates values within the exclusive range
of $10<\Gamma<200$. Intriguingly, in the majority of scenarios, the values of
$\Gamma$ fall between 10 and 40, implying that the model favors a lower
$\Gamma$. Additionally, the plot reveals a symmetrical distribution of
$\theta_{\rm jet}$ and $\theta_{\rm obs}$, with the viable range spanning from
0.02 rad to 0.18 rad. Table 1: Fitting result with the precessing jet model.

$\theta_{\rm jet}$ (rad) |  $\theta_{\rm obs}$ (rad) | $\Gamma$ | ${\rm log}L_{0}$ |  $P$ (s) | $C$ | $\alpha_{1}$ | $\alpha_{2}$ | ${\rm log}t_{b}$
---|---|---|---|---|---|---|---|---
0.04 | 0.07 | 21.47 | $49.61^{+0.14}_{-0.14}$ | $5621^{+63}_{-72}$ | $4.99^{+0.25}_{-0.27}$ | $0.20^{+0.13}_{-0.12}$ | $6.39^{+1.07}_{-0.96}$ | $4.56^{+0.10}_{-0.07}$
0.06 | 0.11 | 14.56 | $49.72^{+0.14}_{-0.14}$ | $5620^{+64}_{-71}$ | $4.99^{+0.26}_{-0.27}$ | $0.20^{+0.13}_{-0.12}$ | $6.37^{+1.07}_{-0.96}$ | $4.56^{+0.10}_{-0.07}$
0.08 | 0.15 | 11.06 | $49.77^{+0.14}_{-0.14}$ | $5622^{+64}_{-71}$ | $4.99^{+0.26}_{-0.27}$ | $0.20^{+0.13}_{-0.12}$ | $6.37^{+1.07}_{-0.95}$ | $4.56^{+0.10}_{-0.07}$

Note. — Based on the Figure 2, we select three groups of $\theta_{\rm jet}$
and $\theta_{\rm obs}$ to test their impact on other parameters, and the
$\Gamma$ is determinate by Equation (15).

Assuming $\theta_{\rm jet}<\theta_{\rm obs}$, we explore the parameters
distribution by considering three groups of $\theta_{\rm jet}$, $\theta_{\rm
obs}$, and $\Gamma$, as shown in Table 1. We employed the MCMC method to
explore the distribution of the parameters, and the results show good
convergence with respect to the precession period. The median values of the
parameters, along with their 1 $\sigma$ uncertainty, have been tabulated in
Table 1. The results from the three different scenarios indicate that these
three parameters have a negligible impact on the period of the precessing jet.
The corner plot in Figure 3 corresponds to the scenario where $\theta_{\rm
jet}=0.06$ rad, $\theta_{\rm obs}=0.11$ rad, and $\Gamma=14.56$. The resulting
lightcurve is also shown in Figure 1. The results of the numerical fitting
indicate that the period of the precessing jet and the characteristic
timescale in the rest frame are $P=5620/(1+z)=771~{}\rm s$ and
$t_{b}=10^{4.56}/(1+z)=4980~{}\rm s$, respectively. Assuming a dimensionless
spin parameter $a\sim 1$ and a central BH mass of $M_{\rm BH}=3{\rm
M_{\odot}}$, the equivalent radius is estimated to be $r=1.13\times
10^{8}~{}\rm cm$. The derived characteristic luminosity suggests that the
magnetic field at the BH horizon before it diffuses out, is as high as $B_{\rm
H,0}=9.49\times 10^{14}$ G.

Figure 3: The contour plot for the posterior distributions of parameters,
corresponds to the scenario where $\theta_{\rm jet}=0.06$ rad, $\theta_{\rm
obs}=0.11$ rad, and $\Gamma=14.56$.

##  4 The Periodicity of observed X-ray flares

A potential periodicity in the detected flares was noticed by Watson et al.
(2006), but no significant QPO signals were identified in their analysis. In
Section 3, the result of the model fitting indicates the existence of the
period of about 5600 s in the observer frame. Therefore, it is valuable to
investigate the possibility of identifying a periodic signal through a time
series analysis of the observed data. In this section, two methods are
employed to test for periodicity.

###  4.1 Preprocessing of observed lightcurve

Section 2.3 indicates that the observed periodic component is amplified with a
power factor, resulting from the Doppler effect, i.e., $L_{\rm EM}\propto
F\propto D^{3}({\rm cos}(\psi(t)))$. The least-squares method, however, is
based on the linear sine function $y=a{\rm cos}(\omega)+b{\rm
sin}(\omega)+const$. Furthermore, the intrinsic luminosity follows a broken-
power-law described trend. Therefore, prior to testing for periodicity, the
observed luminosity $L_{\rm EM}$ is transformed into the logarithmic form. The
intrinsic mean luminosity has

$\displaystyle L_{\rm mean}=D_{\rm mean}^{3}L_{\rm EM}(\psi=0),$ (17)

where $D_{\rm mean}=\frac{1}{2}(D(\psi_{\rm max})+D(\psi_{\rm min}))$.
Therefore the lightcurve transforms to

$\displaystyle L_{T}={\rm log}L_{\rm EM}-{\rm log}L_{\rm mean}.$ (18)

Error propagation gives that $\sigma_{T}=\frac{1}{L_{\rm EM}\times{\rm
ln}10}\sigma_{\rm EM}$, where $\sigma_{\rm EM}$ and $\sigma_{T}$ are the error
of $L_{\rm EM}$ and $L_{T}$, respectively. Following Section 3, we adopt that
$\theta_{\rm jet}=0.06$ rad, $\theta_{\rm obs}=0.11$ rad, and $\Gamma=14.56$,
the derived $L_{T}$ is displayed in figure 4 (a).

###  4.2 Methods and test results

The method of least-squares was proposed to extract periods from inhomogeneous
astronomical lightcurves by Lomb (1976), its reliability tests were
contributed by Scargle (1982), this method is now known as Lomb-Scargle
periodogram (LSP). Zechmeister & Kürster (2009) gave a generalized Lomb-
Scargle periodogram (GLS) that takes errors into account and adds an offset
constant to the sinusoidal function. The wavelet transform overcomes the
limitations of the Fourier transform through mathematical advancements. Foster
(1996) developed the weighted wavelet Z-transform (WWZ) to detect pseudo-
periodic signals in irregular time series. Aydin (2017) developed a Python
program for implementing the WWZ method. The false alarm levels given by
various methods are always based on statistics. However, the power-law
component, red noise, always raises the low-frequency port to a lower false
alarm possibility (FAP). Vaughan (2005) introduced a method for estimating
significance in the context of the background noise following a chi-square
distribution. Furthermore, the background of the periodogram always exhibits
two-smooth-broken-power-law behavior, which complicates the estimation of
background noise. By fitting a first-order autoregressive (AR1) procedure,
Schulz & Mudelsee (2002) develop a Fortran program
(REDFIT222http://www.geo.uni-bremen.de/ mschulz/).

Panels (b) and (c) in Figure 4 represent the REDFIT-based periodogram and the
WWZ-based wavelet transform, respectively. REDFIT program offers confidence
estimates for the corresponding LSP. The confidence based on the Chi-square
distribution of the spectrum is more stringent, with the signal at $P\sim
5600\rm s$ having a confidence level of $Pr>95\%$, while the Monte Carlo
ensemble provides a more flexible limit of $Pr>99\%$. The wavelet transform
reveals a robust and periodic signal at a frequency of approximately $f\sim
1.8\times 10^{-4}~{}\rm Hz$ (corresponding to a period of $P\sim 5600~{}\rm
s$).

Figure 4: (a) The derived lightcurve of $L_{T}$. (b) The periodogram generated
by REDFIT. The significance levels of 95% and 99% are performed in the dashed
line. (c) The periodogram generated by WWZ. A clear periodic signal local at
$f=1.8\times 10^{-4}~{}\rm Hz$.

##  5 Conclusions and Discussions

Unlike a hairless BH, a magnetar possesses rich physical properties such as
rapid rotation, high magnetic field, glitches, and magnetosphere, making it
more conducive to interpreting various astrophysical phenomena. AGN-powered
jets, however, narrate a story of the interaction between a BH and its disk,
facilitated by the presence of the magnetic field. The origin of plateaus in
GRB lightcurves is still a subject of debate. A plateau, followed by either a
shallow or steep decay, can be attributed to either internal or external
origins. The internal plateau, however, is usually attributed to a short-
lived, supermassive magnetar. A BH-based model, by taking the evolution of the
magnetic field at the BH horizon into account, can also replicate a lightcurve
featuring an internal plateau. In this study, we propose that a precessional
BZ jet would imprint a QPO signature on the internal plateau and the
subsequent sharp decay. Such lightcurves cannot be readily interpreted by the
scenario of a short-lived magnetar, as it would have collapsed at the break
time. This model successfully reproduces a peculiar X-ray afterglow of GRB
050904, which consists of nine flares, by assuming that the observed flares
are intrinsic in nature. One suggests that GRB 050904 originates from a BH
central engine, which powers a precessing jet with a period of 771 seconds.

Chromatic X-ray plateaus and optical afterglows have been extensively
observed, such as GRB 070110 (Troja et al., 2007). In GRB 050904, the observed
optical and near-infrared afterglow can be well explained by the standard
afterglow model (e.g., Wei et al., 2006; Gou et al., 2007), while the X-ray
flares attributed to internal dissipation of precessing jet. This fact implies
a connection between X-ray flares and plateaus, in the afterglow of GRB
050904. The results of the periodicity test indicate that the confidence level
for the periodicity of GRB 050904 might not exceed $99\%$, a limitation
largely attributable to the observational qualities. GRB 050904 is not a
singular example presenting a potential QPO in the extensive X-ray afterglows
collected by Swift/XRT, for example, GRB 130925A is another source to exhibit
possible QPO behavior (Hou et al., 2014). However, Earth’s shielding limits
the ability of the XRT to capture comprehensive lightcurves of these GRBs. The
synergy between XRT and the forthcoming Einstein Probe (EP; Yuan et al., 2022)
and Space-based Multiband Astronomical Variable Object Monitor (SVOM; Wei et
al., 2016) observations of the same GRB afterglow is anticipated to yield a
holistic lightcurve of these GRB afterglows. Some researchers have suggested
that the prompt emission possesses potential periodicity on time scales of
seconds or less (Zhang et al., 2022; Xiao et al., 2022; Wang et al., 2022;
Zhang et al., 2023). Then whether these similar short-period activities exist
in the X-ray plateau is very important for understanding the central engine of
GRBs. However, the sensitivity of XRT is insufficient for adequately capturing
photons to discern these short-period activities. NewAthena (see also Athena:
Advanced Telescope for High-ENergy Astrophysics; Barcons et al., 2015) may
show extraordinary talent in the research of the periodicity in X-ray
afterglows. NewAthena/WFI (Wide Field Imager) detection capability surpasses
the XRT by more than an order of magnitude, which will enable a detailed
examination of the temporal evolution of X-ray afterglows. Furthermore, EP/FXT
(Follow-up X-ray Telescope) also exhibits enhanced performance in the lower
energy band (0.5 - 2 keV) compared to XRT.

We acknowledge the use of the public data from the Swift data archive and the
UK Swift Science Data Center. We gratefully thank the anonymous referee for
helpful comments to improve this paper. We thank Dr. Xiang Li for useful
discussion. This work was supported by NSFC (No. 12073080, 11933010, 11921003,
12303050) and by the Chinese Academy of Sciences via the Key Research Program
of Frontier Sciences (No. QYZDJ-SSW-SYS024).

## References

  * Aydin (2017) Aydin M. E., 2017,. eaydin/WWZ: First release, doi:10.5281/zenodo.375648, https://doi.org/10.5281/zenodo.375648
  * Barcons et al. (2015) Barcons, X., Nandra, K., Barret, D., et al. 2015, Journal of Physics Conference Series, 610, 012008. doi:10.1088/1742-6596/610/1/012008
  * Blandford & Znajek (1977) Blandford, R. D. & Znajek, R. L. 1977, MNRAS, 179, 433. doi:10.1093/mnras/179.3.433
  * Bloom et al. (2001) Bloom, J. S., Frail, D. A., & Sari, R. 2001, AJ, 121, 2879. doi:10.1086/321093
  * Chevalier (1989) Chevalier, R. A. 1989, ApJ, 346, 847. doi:10.1086/168066
  * Costa et al. (1997) Costa, E., Frontera, F., Heise, J., et al. 1997, Nature, 387, 783. doi:10.1038/42885
  * Cummings et al. (2005) Cummings, J., Angelini, L., Barthelmy, S., et al. 2005, GRB Coordinates Network, Circular Service, No. 3910, #1 (2005), 3910
  * Dai & Lu (1998) Dai, Z. G. & Lu, T. 1998, A&A, 333, L87. doi:10.48550/arXiv.astro-ph/9810402
  * Dereli-Bégué et al. (2022) Dereli-Bégué, H., Pe’er, A., Ryde, F., et al. 2022, Nature Communications, 13, 5611. doi:10.1038/s41467-022-32881-1
  * Evans et al. (2009) Evans, P. A., Beardmore, A. P., Page, K. L., et al. 2009, MNRAS, 397, 1177. doi:10.1111/j.1365-2966.2009.14913.x
  * Foreman-Mackey et al. (2013) Foreman-Mackey, D., Hogg, D. W., Lang, D., et al. 2013, PASP, 125, 306. doi:10.1086/670067
  * Foster (1996) Foster, G. 1996, AJ, 112, 1709. doi:10.1086/118137
  * Frail et al. (2006) Frail, D. A., Cameron, P. B., Kasliwal, M., et al. 2006, ApJ, 646, L99. doi:10.1086/506934
  * Gou et al. (2007) Gou, L.-J., Fox, D. B., & Mészáros, P. 2007, ApJ, 668, 1083. doi:10.1086/520699
  * Hou et al. (2014) Hou, S.-J., Liu, T., Gu, W.-M., et al. 2014, ApJ, 781, L19. doi:10.1088/2041-8205/781/1/L19
  * Ioka et al. (2006) Ioka, K., Toma, K., Yamazaki, R., et al. 2006, A&A, 458, 7. doi:10.1051/0004-6361:20064939
  * Kawai et al. (2006) Kawai, N., Kosugi, G., Aoki, K., et al. 2006, Nature, 440, 184. doi:10.1038/nature04498
  * King et al. (2005) King, A., O’Brien, P. T., Goad, M. R., et al. 2005, ApJ, 630, L113. doi:10.1086/496881
  * Kisaka & Ioka (2015) Kisaka, S. & Ioka, K. 2015, ApJ, 804, L16. doi:10.1088/2041-8205/804/1/L16
  * Lei et al. (2007) Lei, W. H., Wang, D. X., Gong, B. P., et al. 2007, A&A, 468, 563. doi:10.1051/0004-6361:20066219
  * Lei et al. (2013) Lei, W.-H., Zhang, B., & Gao, H. 2013, ApJ, 762, 98. doi:10.1088/0004-637X/762/2/98
  * Lense & Thirring (1918) Lense, J. & Thirring, H. 1918, Physikalische Zeitschrift, 19, 156
  * Li et al. (2022) Li, X., Ge, M., Lin, L., et al. 2022, ApJ, 931, 56. doi:10.3847/1538-4357/ac6587
  * Li et al. (2023) Li, Y., Shen, R.-F., & Zhang, B.-B. 2023, ApJ, 955, 98. doi:10.3847/1538-4357/acefbf
  * Liang et al. (2007) Liang, E.-W., Zhang, B.-B., & Zhang, B. 2007, ApJ, 670, 565. doi:10.1086/521870
  * Liu et al. (2010) Liu, T., Liang, E.-W., Gu, W.-M., et al. 2010, A&A, 516, A16. doi:10.1051/0004-6361/200913447
  * Lomb (1976) Lomb, N. R. 1976, Ap&SS, 39, 447. doi:10.1007/BF00648343
  * Lu (1990) Lu, J. F. 1990, A&A, 229, 424
  * Lyons et al. (2010) Lyons, N., O’Brien, P. T., Zhang, B., et al. 2010, MNRAS, 402, 705. doi:10.1111/j.1365-2966.2009.15538.x
  * Nousek et al. (2006) Nousek, J. A., Kouveliotou, C., Grupe, D., et al. 2006, ApJ, 642, 389. doi:10.1086/500724
  * Peng et al. (2005) Peng, F., Königl, A., & Granot, J. 2005, ApJ, 626, 966. doi:10.1086/430045
  * Perna et al. (2006) Perna, R., Armitage, P. J., & Zhang, B. 2006, ApJ, 636, L29. doi:10.1086/499775
  * Planck Collaboration et al. (2020) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020, A&A, 641, A6. doi:10.1051/0004-6361/201833910
  * Popham et al. (1999) Popham, R., Woosley, S. E., & Fryer, C. 1999, ApJ, 518, 356. doi:10.1086/307259
  * Portegies Zwart et al. (1999) Portegies Zwart, S. F., Lee, C.-H., & Lee, H. K. 1999, ApJ, 520, 666. doi:10.1086/307471
  * Rowlinson et al. (2013) Rowlinson, A., O’Brien, P. T., Metzger, B. D., et al. 2013, MNRAS, 430, 1061. doi:10.1093/mnras/sts683
  * Rowlinson et al. (2010) Rowlinson, A., O’Brien, P. T., Tanvir, N. R., et al. 2010, MNRAS, 409, 531. doi:10.1111/j.1365-2966.2010.17354.x
  * Sakamoto et al. (2005) Sakamoto, T., Barbier, L., Barthelmy, S., et al. 2005, GRB Coordinates Network, Circular Service, No. 3938, #1 (2005), 3938
  * Sarazin et al. (1980) Sarazin, C. L., Begelman, M. C., & Hatchett, S. P. 1980, ApJ, 238, L129. doi:10.1086/183272
  * Şaşmaz Muş et al. (2019) Şaşmaz Muş, S., Çıkıntoğlu, S., Aygün, U., et al. 2019, ApJ, 886, 5. doi:10.3847/1538-4357/ab498c
  * Scargle (1982) Scargle, J. D. 1982, ApJ, 263, 835. doi:10.1086/160554
  * Schulz & Mudelsee (2002) Schulz, M. & Mudelsee, M. 2002, Computers and Geosciences, 28, 421. doi:10.1016/S0098-3004(01)00044-9
  * Suvorov & Kokkotas (2020) Suvorov, A. G. & Kokkotas, K. D. 2020, ApJ, 892, L34. doi:10.3847/2041-8213/ab8296
  * Tagliaferri et al. (2005) Tagliaferri, G., Antonelli, L. A., Chincarini, G., et al. 2005, A&A, 443, L1. doi:10.1051/0004-6361:200500196
  * Tchekhovskoy & Giannios (2015) Tchekhovskoy, A. & Giannios, D. 2015, MNRAS, 447, 327. doi:10.1093/mnras/stu2229
  * Tchekhovskoy et al. (2011) Tchekhovskoy, A., Narayan, R., & McKinney, J. C. 2011, MNRAS, 418, L79. doi:10.1111/j.1745-3933.2011.01147.x
  * Troja et al. (2007) Troja, E., Cusumano, G., O’Brien, P. T., et al. 2007, ApJ, 665, 599. doi:10.1086/519450
  * Usov (1992) Usov, V. V. 1992, Nature, 357, 472. doi:10.1038/357472a0
  * van Paradijs et al. (1997) van Paradijs, J., Groot, P. J., Galama, T., et al. 1997, Nature, 386, 686. doi:10.1038/386686a0
  * Vaughan (2005) Vaughan, S. 2005, A&A, 431, 391. doi:10.1051/0004-6361:20041453
  * Wang et al. (2022) Wang, Y., Jiang, L.-Y., & Ren, J. 2022, ApJ, 935, 179. doi:10.3847/1538-4357/ac82ec
  * Watson et al. (2006) Watson, D., Reeves, J. N., Hjorth, J., et al. 2006, ApJ, 637, L69. doi:10.1086/501004
  * Wei et al. (2006) Wei, D. M., Yan, T., & Fan, Y. Z. 2006, ApJ, 636, L69. doi:10.1086/500259
  * Wei et al. (2016) Wei, J., Cordier, B., Antier, S., et al. 2016, arXiv:1610.06892. doi:10.48550/arXiv.1610.06892
  * Wei & Fan (2007) Wei, D.-M. & Fan, Y.-Z. 2007, Chinese J. Astron. Astrophys., 7, 509. doi:10.1088/1009-9271/7/4/06
  * Wilkins (1972) Wilkins, D. C. 1972, Phys. Rev. D, 5, 814. doi:10.1103/PhysRevD.5.814
  * Xiao & Dai (2019) Xiao, D. & Dai, Z.-G. 2019, ApJ, 878, 62. doi:10.3847/1538-4357/ab12da
  * Xiao et al. (2022) Xiao, S., Zhang, Y.-Q., Zhu, Z.-P., et al. 2022, arXiv:2205.02186. doi:10.48550/arXiv.2205.02186
  * Yuan et al. (2022) Yuan, W., Zhang, C., Chen, Y., et al. 2022, Handbook of X-ray and Gamma-ray Astrophysics, 86. doi:10.1007/978-981-16-4544-0_151-1
  * Zamaninasab et al. (2014) Zamaninasab, M., Clausen-Brown, E., Savolainen, T., et al. 2014, Nature, 510, 126. doi:10.1038/nature13399
  * Zechmeister & Kürster (2009) Zechmeister, M. & Kürster, M. 2009, A&A, 496, 577. doi:10.1051/0004-6361:200811296
  * Zhang et al. (2022) Zhang, B.-B., Zhang, Z. J., Zou, J.-H., et al. 2022, arXiv:2205.07670. doi:10.48550/arXiv.2205.07670
  * Zhang et al. (2006) Zhang, B., Fan, Y. Z., Dyks, J., et al. 2006, ApJ, 642, 354. doi:10.1086/500723
  * Zhang et al. (2007) Zhang, B., Liang, E., Page, K. L., et al. 2007, ApJ, 655, 989. doi:10.1086/510110
  * Zhang et al. (2023) Zhang, Z., Iris Yin, Y.-H., Wang, C., et al. 2023, Research in Astronomy and Astrophysics, 23, 115023. doi:10.1088/1674-4527/acfa59
  * Zhang & Mészáros (2001) Zhang, B. & Mészáros, P. 2001, ApJ, 552, L35. doi:10.1086/320255
  * Zheng et al. (2021) Zheng, T.-C., Li, L., Zou, L., et al. 2021, Research in Astronomy and Astrophysics, 21, 300. doi:10.1088/1674-4527/21/12/300
  * Zou et al. (2021) Zou, L., Zheng, T.-C., Yang, X., et al. 2021, ApJ, 921, L1. doi:10.3847/2041-8213/ac2ee4
  * Zou & Liang (2022) Zou, L. & Liang, E.-W. 2022, MNRAS, 513, L89. doi:10.1093/mnrasl/slac040


# Sparse Recovery Analysis of Preconditioned Frames via Convex Optimization

Pradip Sasmal, Prasad Theeda, Phanindra Jampana and C. S. Sastry P. Sasmal, P.
Theeda and C. Sastry are with the Department of Mathematics, Indian Institute
of Technology, HyderabadPhanindra Jampana is with the Department of Chemical
Engineering, Indian Institute of Technology, HyderabadManuscript received
ABCD; revised CDEF.

###### Abstract

Orthogonal Matching Pursuit and Basis Pursuit are popular reconstruction
algorithms for recovery of sparse signals. The exact recovery property of both
the methods has a relation with the coherence of the underlying redundant
dictionary, i.e. a frame. A frame with low coherence provides better
guarantees for exact recovery. An equivalent formulation of the associated
linear system is obtained via premultiplication by a non-singular matrix. In
view of bounds that guarantee sparse recovery, it is very useful to generate
the preconditioner in such way that the preconditioned frame has low coherence
as compared to the original. In this paper, we discuss the impact of
preconditioning on sparse recovery. Further, we formulate a convex
optimization problem for designing the preconditioner that yields a frame with
improved coherence. In addition to reducing coherence, we focus on designing
well conditioned frames and numerically study the relationship between the
condition number of the preconditioner and the coherence of the new frame.
Alongside theoretical justifications, we demonstrate through simulations the
efficacy of the preconditioner in reducing coherence as well as recovering
sparse signals.

###### Index Terms:

Compressed Sensing, Convex Optimization, Incoherent frames, Pre-conditioning,
Semidefinite Programming, Unit Norm Tight Frames.

##  I Introduction

Compressed Sensing (CS) [21, 23, 24, 25, 41] has emerged as a powerful and
effective tool towards producing sparse signal representations. CS provides
stable recovery of a sparse signal form an under-determined linear system of
equations. Performance of several sparse recovery algorithms like Basis
Pursuit (BP) and Orthogonal Matching Pursuit (OMP) depends on the coherence of
the underlying frame. Frames that satisfy the Restricted Isometry Property
(RIP) [26, 27] are known to allow for exact recovery of sparse signals from a
few of their linear measurements. However, in general, it is computationally
hard to verify the Restricted Isometry Property (RIP) of a given frame. In
contrast, the coherence (the largest absolute normalized inner product between
two distinct columns) of a frame is an easily computable quantity that asserts
RIP up to certain order [28].

Frames with small coherence are said to be incoherent. For a fixed number of
elements, frames with the smallest coherence are called Grassmannian [5]. The
lowest bound on the minimal achievable correlation for any frame, known as
Welch bound [14], is given by $\sqrt{\frac{M-m}{m(M-1)}},$ where $m$ is the
dimension of the ambient space and $M$ is the number of frame elements.
Incoherent frames and especially Incoherent Unit Norm Tight Frames (UNTFs)
play a significant role due to their ability in providing stable, sparse
representations and effectiveness in the construction of signature sequences
in CDMA systems [8, 9]. However, construction of such frames is known to be
very difficult.

In [22, 23], J. Tropp et.al., and M. Elad have used an alternating projection
method to produce incoherent frames. In [33, 34], C. Rusu et. al., have
proposed a convex optimization technique applied on a random Gaussian matrix
for designing incoherent frames. In [12], B. G. Bodmann et. al. have
constructed UNTFs by differential equation based techniques. P. G. Casazza et.
al. [13] have used a gradient descent algorithm for realizing UNTFs. In [35],
E. Tsiligianni et. al. have proposed an iterative process on the Gram matrix
of $\Phi$ to obtain an incoherent UNTF.

In [36], a preconditioning technique has been employed to design an incoherent
unit norm frame via shrinkage operation on the off-diagonal entries of the
Gram matrix of $\Phi$ and the incoherent unit norm frame so obtained is near
to an UNTF. The technique may be summarized as follows: the initial frame
$\Phi$ is premultiplied by a Gaussian matrix $G$ followed by a normalization
step. Then the Gram matrix $H$ of $G\Phi$ is formed and the shrinkage
operation, decimating the entries above $\frac{1}{\sqrt{m}}$ in magnitude, is
applied on $H$ to form $H^{\prime}$. Subsequently, the premultiplier
$\Phi^{\prime\prime}$ is obtained from
$H^{\prime\prime}=(\Phi^{\prime\prime})^{T}\Phi^{\prime\prime}$, where
$H^{\prime\prime}$ is the best rank-$m$ approximation of $H^{\prime}$. This
process is repeated iteratively for generating incoherent frames. This method,
however, is not known to provide theoretical guarantees for the convergence of
the iterative process.

In many applications, the sensing matrix may not match with the incoherent
frames developed by existing methods mentioned above. While these methods
focus on constructing incoherent frames directly, we approach this problem
from the perspective of an already existing linear system and develop
incoherent frames via preconditioning.

Coherence of $G\Phi$ is in general a non-convex function in $G$ for a given
frame $\Phi$. However, under the condition that $G\Phi$ is a unit norm frame,
the optimization problem becomes tractable (in fact, it becomes a semi-
definite program (SDP)). In the case of noisy observations, in addition to
small coherence, it is also desirable to obtain a preconditioner which has a
small condition number. This problem can also be formulated as an SDP. Besides
formulating the SDP problems, in this paper, we also give a sufficient
condition for the existence of an invertible $G$ so that there is a strict
fall in coherence, i.e. $\mu(G\Phi)<\mu(\Phi).$ The condition can be verified
by checking a linear system of equations for infeasibility.

Preconditioning may affect the performance guarantees of OMP but BP remains
unaffected. However, the existing coherence based bounds for BP can be
enlarged using the idea of preconditioning. In the case where $G$ is diagonal,
results from frame theory give analytical conditions for strict fall in
coherence as opposed to the sufficient conditions in the general case.

The paper is organized in several sections. In Section 2, we provide basics of
frame theory and compressed sensing. In Sections 3 and 4, we present the
effect of preconditioning on sparse recovery algorithms and our proposed
convex optimization method respectively. In Sections 5 and 6, we study
respectively the analysis of optimal solution of the semidefinite programming
(SDP) problem and the proposed convex optimization to obtain preconditioner in
noisy cases. In Section 7, we demonstrate our simulation results. The paper
ends with concluding remarks in the final section.

##  II Basics of Frame theory and Compressed Sensing

###  II-A Frame Theory

Frames are overcomplete spanning systems, which are introduced as a
generalization of bases [1, 2, 4, 37]. Frame theory has deep connections with
Harmonic analysis, Operator theory, Coding theory [10] and Quantum theory
[11]. Due to its widespread applicability, the area of frames has become an
active area of research for many researchers from several fields. In signal
processing, frames play a significant role in sparse signal recovery [3, 28].

A family of vectors $\\{\phi_{i}\\}^{M}_{i=1}$ in $\mathbb{R}^{m}$ is called a
frame for $\mathbb{R}^{m}$, if there exist constants $0<A\leq B<\infty$ such
that

$\displaystyle A\left\|z\right\|^{2}\leq\sum^{M}_{i=1}\left|\left\langle
z,\phi_{i}\right\rangle\right|^{2}\leq B\left\|z\right\|^{2},\forall
z\in\mathbb{R}^{m},$ (1)

where $A,B$ are called the lower and upper frame bounds respectively [1]. The
matrix $\Phi_{m\times M}=[\phi_{1}\dots\phi_{M}]$ with $\phi_{i}$ as columns
is known as the frame synthesis operator. The adjoint of synthesis operator
$\Phi$ is known as analysis operator $\Phi^{*}=\Phi^{T}$. The frame operator
$F_{\Phi}$ is given by $F_{\Phi}=\Phi\Phi^{T}.$ In this paper we refer to
$\Phi$ as a frame and also as a matrix depending on the context. Frames are
characterized depending on their properties as outlined below:

  * •

If $A=B$, then $\\{\phi_{i}\\}^{M}_{i=1}$ is an $A-$tight frame or simply a
tight frame.

  * •

If there exists a constant $d$ such that
$|\left\langle\phi_{i},\phi_{j}\right\rangle|=d,$ for $1\leq i<j\leq M,$ then
$\\{\phi_{i}\\}^{M}_{i=1}$ is an equiangular frame.

  * •

If there exits a constant $c$ such that $\left\|\phi_{i}\right\|_{2}=c$ for
all $i=1,2,\ldots,n,$ then $\\{\phi_{i}\\}^{M}_{i=1}$ is an equal norm frame.
If $c=1,$ then it is called a unit-norm frame.

  * •

If a frame is both unit norm and tight, it is called a unit norm tight frame
(UNTF).

  * •

If a frame is both UNTF and equiangular, it is called an equiangular tight
frame (ETF).

UNTFs are an important class of frames as they have good conditioning and
provide stable representation. For a given frame $\Phi$, the frame potential
is defined by

$FP(\Phi)=\sum^{M}_{i,j=1}|\langle\phi_{i},\phi_{j}\rangle|^{2}=\|H\|^{2}_{F},$

where $H=\Phi^{T}\Phi$ and $\|\bullet\|_{F}$ denotes the Frobenius norm. For
an arbitrary frame $\Phi$, $FP(\Phi)\leq\frac{M^{2}}{m}$ and equality holds
when $\Phi$ is a unit norm tight frame. A UNTF $\\{\phi_{i}\\}^{M}_{i=1}$
exists only for $A=\frac{M}{m}.$ ETFs are known as optimal Grasssmanian frames
as their coherence touches the Welch bound [14]. It is known that these frames
exist only for certain frame dimensions such as $M\leq\frac{m(m+1)}{2}$.

###  II-B Compressed Sensing

The objective of Compressed Sensing (CS) is to recover $x\in\mathbb{R}^{M}$
from a few of its linear measurements $y\in\mathbb{R}^{m}$ through a stable
and efficient reconstruction process via the concept of sparsity. From the
measurement vector $y$ and the sensing mechanism, one obtains a system $y=\Phi
x$, where $\Phi$ is an $m\times M\;(m<M)$ matrix. Sparsity is measured by
$\|\cdot\|_{0}$ norm where $\|x\|_{0}:=|\\{j\in\\{1,2,\dots,M\\}:x_{j}\neq
0\\}|$. Finding the sparsest solution can be formulated as the following
minimization problem,

$P_{0}(\Phi,y):\min_{x}\|{x}\|_{0}\;\mbox{subject to}\quad\Phi x=y.$

This is a combinatorial minimization problem and is known to be NP-hard [16].
One may use greedy methods [7] or convex relaxation of $P_{0}(\Phi,y)$ problem
to recover the $k$-sparse signal $x$ (that is, $\|x\|_{0}\leq k$). The convex
relaxation of $P_{0}(\Phi,y)$ problem can be posed as [17], [19],

$P_{1}(\Phi,y):\min_{x}\|{x}\|_{1}\;\mbox{subject to}\quad\Phi x=y.$

Candes and Tao [18] have introduced the following isometry condition on
matrices $\Phi$ and have shown that it results in sufficient conditions for
exact recovery. An $m\times M$ matrix $\Phi$ is said to satisfy the Restricted
Isometry Property (RIP) of order $k$ with constant $\delta_{k}$
$(0<\delta_{k}<1)$ if for all vectors $x\in\mathbb{R}^{M}$ with $\|x\|_{0}\leq
k$, we have

$(1-\delta_{k})\left\|x\right\|^{2}_{2}\leq\left\|\Phi
x\right\|^{2}_{2}\leq(1+\delta_{k})\left\|x\right\|^{2}_{2}.$ (2)

Roughly speaking, RIP measures the “overall conditioning" of the set of
$m\times k$ submatrices of $\Phi.$ Consequently, a smaller $\delta_{k}$
implies better sparse recovery properties. The following theorem [19]
establishes the equivalence between $P_{0}$ and $P_{1}$ problems:

######  Theorem II.1.

Suppose an $m\times M$ matrix $\Phi$ has the $(2k,\delta)$ restricted isometry
property with $\delta<\sqrt{2}-1$, then $P_{0}$ and $P_{1}$ have the same
$k-$sparse solution if $P_{0}$ has a $k-$sparse solution.

The coherence of $\Phi$ is given by

$\mu(\Phi)=\max_{1\leq\;i,j\leq\;M,\;i\neq
j}\frac{|\;\phi_{i}^{T}\phi_{j}|}{\|\phi_{i}\|_{2}\|\phi_{j}\|_{2}}.$

The following proposition [16] relates $\delta_{k}$ and $\mu.$

######  Proposition II.2.

Suppose that $\phi_{1},\ldots,\phi_{M}$ are the unit norm columns of the
matrix $\Phi$ with coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$
with constant $\delta_{k}=(k-1)\mu$.

The above relation indicates that our desire to have smaller $\delta_{k}$ is
achievable by producing matrices with smaller coherence. It is to be noted
however that there exist fundamental limitations in constructing matrices with
large RIP orders using coherence based arguments [16].

Coherence based techniques are used in establishing the guaranteed recovery of
sparse signals via Orthogonal Matching Pursuit (OMP) or Basis Pursuit (BP), as
summarized by the following result [20].

######  Theorem II.3.

An arbitrary $k-$sparse signal $x$ can be uniquely recovered as a solution to
problems $P_{0}(\Phi,y)$ (using OMP) and $P_{1}(\Phi,y)$, provided

$k<\frac{1}{2}\biggl{(}1+\frac{1}{\mu(\Phi)}\biggl{)}.$ (3)

##  III Effect of preconditioning on OMP and BP

For a non-singular matrix $G,$ the linear system $\Phi x=y$ is the same as
$G\Phi x=Gy$ and hence the problems $P_{0}(\Phi,y)$, $P_{0}(G\Phi,Gy)$ and
$P_{1}(\Phi,y)$, $P_{1}(G\Phi,Gy)$ are equivalent respectively.

OMP is an iterative greedy algorithm by nature. It selects at every iteration
the frame element which has the maximum correlation with the residual at that
step and provides an orthogonal projection of the signal on the space spanned
by the already selected frame atoms. In general, when OMP is used, the
solutions of $P_{0}(\Phi,y)$ and $P_{0}(G\Phi,Gy)$ may not be the same. It can
also be noted that the bounds in (3) may also differ as $\Phi$ and $G\Phi$ can
have different coherences.

In contrast, as $P_{1}(G\Phi,Gy)$ is typically solved as a linear program, the
solutions of $P_{1}(\Phi,y)$ and $P_{1}(G\Phi,Gy)$ remain the same. In view of
bounds such as (3), one obtains better theoretical guarantee for the system
possessing $\tilde{G}\Phi$ as its underlying sensing matrix, where $\tilde{G}$
is given by

$\tilde{G}=\underset{G~{}\text{non-singular}}{\arg\min}\mu(G\Phi)$ (4)

Consequently, any $k-$sparse solution of $\tilde{G}y=\tilde{G}\Phi x$ can be
uniquely recovered whenever

$k<\frac{1}{2}\biggl{(}1+\frac{1}{\mu(\tilde{G}\Phi)}\biggl{)}.$

As $P_{1}(\Phi,y)$ and $P_{1}(\tilde{G}\Phi,\tilde{G}y)$ are equivalent, this
implies that any $k-$sparse solution of $y=\Phi x$ can also be uniquely
recovered whenever the above bound is satisfied. This can be summarized by the
following theorem.

######  Theorem III.1.

Let $\tilde{G}=\underset{G~{}\text{non-singular}}{\arg\min}\mu(G\Phi)$ and
assume that $\mu_{\tilde{G}\phi}$ is well defined. An arbitrary $k-$sparse
signal $x$ can be uniquely recovered as a solution to $P_{1}(\Phi,y)$,
provided

$k<\frac{1}{2}\biggl{(}1+\frac{1}{\mu(\tilde{G}\Phi)}\biggl{)}$ (5)

###### Proof.

If $\tilde{G}$ is non-singular, the proof is trivial. Assuming $\tilde{G}$ is
singular, we can obtain a sequence of non-singular matrices $G_{n}$ so that
$G_{n}\to\tilde{G}$. Hence,

$k<\frac{1}{2}\biggl{(}1+\frac{1}{\mu(G_{n}\Phi)}\biggl{)}~{}\forall
n=1,2,\dots$

Applying a limit on both sides and noting that $\mu(G\Phi)$ is continuous in
$G$, we obtain the desired result. ∎

If the minimum is attained in (4), the bound stated in (5) is applicable to
the system $\tilde{G}y=\tilde{G}\Phi x$ in recovering sparse solutions via OMP
as well. Nevertheless, in contrast to solving $P_{1}(\Phi,y)$ using linear
programming, OMP used to solve $P_{0}(\Phi,y)$ where $y=\Phi
x,\|x\|_{0}\in\biggl{[}\frac{1}{2}\biggl{(}1+\frac{1}{\mu_{\Phi}}\biggl{)},\frac{1}{2}\biggl{(}1+\frac{1}{\mu_{\tilde{G}\Phi}}\biggl{)}\biggl{]}$
may not recover the solution. In other words, for $k$ lying between the values
on the right hand sides of (3) and (5), OMP run on $y=\Phi x$ and
$\tilde{G}y=\tilde{G}\Phi x$ may yield different support sets.

##  IV Preconditioning via Convex Optimization

In this section, starting from a frame $\Phi=\\{\phi_{i}\\}^{M}_{i=1}$, we
discuss our methodology towards designing a suitable preconditioner that acts
on $\Phi$ to produce a new frame with smaller coherence. Without loss of
generality, we assume that $\Phi$ is an unit norm frame, that is,

$\|\phi_{i}\|_{2}=1,\quad\forall i=1,\dots,M.$

For a given frame $\Phi,$ the problem of finding a preconditioner $G$ that
yields an incoherent frame $G\Phi$ may be posed in the following manner:

$C_{0}:\arg\min_{G}\max_{i\neq j}\frac{|\langle
G\phi_{i},G\phi_{j}\rangle|}{\|G\phi_{i}\|_{2}\|G\phi_{j}\|_{2}}.$

It can be noted that $C_{0}$ is a non-convex problem in general due to the
denominator terms involving $G$ in the expression for coherence. However, with
the assumption of unit norm condition,

$\|G\phi_{i}\|_{2}=1,\quad\forall i=1,\dots,M.$

the relaxed $C_{0}$ problem, i.e.,

$C^{\prime}_{0}:\min_{G}\max_{i\neq j}|\langle G\phi_{i},G\phi_{j}\rangle|.$

becomes tractable. The full classification of preconditioners which preserve
the unit norm condition has been discussed in [37].

######  Theorem IV.1.

Let $\Phi=\\{\phi_{i}\\}^{M}_{i=1}$ be an unit norm frame for $\mathbb{R}^{m}$
and let $G$ be an invertible operator on $\mathbb{R}^{m}$ such that $G^{T}G$
has eigen vectors $\mathbb{E}=\\{e^{G}_{j}\\}^{m}_{j=1}$ with respective eigen
values $\\{\lambda^{G}_{j}\\}^{m}_{j=1},$ then $G$ maps $\Phi$ to an unit norm
frame, that is, $\|G\phi_{i}\|_{2}=1$ if and only if
$(\lambda^{G}_{1}-1,\dots,\lambda^{G}_{m}-1)^{m}_{j=1}\bot~{}\mathbb{R}(\Phi,\mathbb{E})=\text{span}\\{(|\left\langle\phi_{i},e^{G}_{j}\right\rangle|^{2})^{m}_{j=1}\\}^{M}_{i=1}.$

A simple example is any unitary operator $U$. $U$ maps $\Phi$ to a unit norm
frame as $\|U\phi_{i}\|_{2}=1$. However, as $\left\langle
U\phi_{i},U\phi_{j}\right\rangle=\left\langle\phi_{i},\phi_{j}\right\rangle,$
$\mu(U\Phi)=\mu(\Phi)$, there is no improvement in coherence.

For a non-singular matrix $G$, the gram matrix of $G\Phi$ is given by
$\Phi^{T}X\Phi,$ where $X=G^{T}G$ is a symmetric positive definite matrix. We
denote the set of symmetric positive definite matrices of order $m$ by
$S^{m}_{++}$. Let $S_{\Phi}=\\{X\in
S^{m}_{++}:\mbox{diag}(\Phi^{T}X\Phi)={\bf{1}}\\}=\\{X\in
S^{m}_{++}:\phi^{T}_{i}X\phi_{i}=1,\forall i=1,\dots,M\\},$ where $\bf{1}$ is
a vector of length $M$ with all its entries equal to unity. It is easy to
check that $S_{\Phi}$ is a convex set. Also, $S_{\Phi}\neq\emptyset$ as
$U_{m}\in S_{\Phi},$ where $U_{m}$ is any unitary matrix of size $m\times m$.
It can be noted that the coherence of $G\Phi$ is given by

$c^{X}_{\Phi}=\max_{i\neq j}|\phi^{T}_{i}X\phi_{j}|,$

which is a convex function of $X$.

The convexity of $S_{\Phi}$ and $c^{X}_{\Phi}$ motivates us to repose
$C^{\prime}_{0}$ as:

$C_{1}:\min_{X\in S_{\Phi}}\max_{i\neq j}|\phi^{T}_{i}X\phi_{j}|;$

However, as $S_{\Phi}$ may not be closed, $C_{1}$ might not have a solution.
We relax the set $S_{\Phi}$ so that the feasible region is guaranteed to be
closed. A natural way is to consider the class of symmetric semi-positive
definite matrices ($S^{m}_{+}$) in the place of symmetric positive definite
matrices $S^{m}_{++}$. We constitute the following feasible set

$S^{\prime}_{\Phi}=\\{X\in S^{m}_{+}:\mbox{diag}(\Phi^{T}X\Phi)=\bf{1}\\},$

which is closed and convex. This consideration allows us to have the following
relaxed formulation of $C_{1}$,

$C_{1}^{\prime}:\begin{aligned} &\underset{X,q}{\text{max}}&&(-q)\\\
&\text{subject to}&&\phi^{T}_{i}X\phi_{i}=1,\forall i=1,\dots,M;\\\
&&&\phi^{T}_{i}X\phi_{j}\leq q,\forall 1\leq i<j\leq M;\\\
&&&\phi^{T}_{i}X\phi_{j}\geq-q,\forall 1\leq i<j\leq M;\\\ &&&X\geq 0\\\
&&&q\geq 0.\end{aligned}$

It may be observed that $q$ acts as the coherence of the matrix $G\Phi$.

######  Remark IV.2.

Let the Cholesky decomposition of $X$ be $L^{T}L$, then the matrix $G$ can be
obtained as $L$.

###  IV-A Preconditioner producing frame near to an UNTF:

We now focus on obtaining a preconditioner that produces a frame that is near
to an UNTF [troop_2005]. The solution to the nearness problem follows from the
following result from frame theory [35].

######  Theorem IV.3.

For a given frame $\Psi_{m\times M}$, suppose the singular value decomposition
(SVD) is given by $\Psi=U\Sigma V^{*}$ . With respect to the Frobenius norm,
the nearest unique $\alpha-$tight frame from $\Psi$ is given by
$N_{\Psi}=\sqrt{\alpha}UV^{*}$. One may compute $UV^{*}$ using the formula
$(\Psi\Psi^{T})^{-\frac{1}{2}}\Psi.$

Let the SVD of $G\Phi$ ($G$ being obtained by solving $C_{1}$ problem) be
$G\Phi=U\Sigma V^{*}$, then the nearest $\frac{M}{m}-$tight frame from $G\Phi$
is given by $N_{G\Phi}=\left(\sqrt{\frac{M}{m}}\right)UV^{*}$, which is near
to an UNTF [36]. Note that if we let
$G^{{}^{\prime}}_{1}=\left(\sqrt{\frac{M}{m}}\right)U\Sigma^{-1}U^{T}$, where
$\Sigma^{-1}$ is obtained from the $m\times m$ principle minor of $\Sigma$ by
replacing the non-zero diagonal entries with their reciprocals then by
definition $G^{{}^{\prime}}_{1}$ is non-singular and it is easy to check that
$G^{{}^{\prime}}_{1}G\Phi=N_{G\Phi}=G_{1}\Phi,$ where
$G_{1}=G^{{}^{\prime}}_{1}G.$ So $N_{G\Phi}$ can be obtained from $\Phi$ by
premultiplying with $G_{1}.$

###  IV-B Diagonal Preconditioner

Before dealing with a general preconditioner $G$, we first analyze the
optimization problem $C_{1}^{\prime}$ for diagonal operators that belong to
$S_{\Phi}$. The following theorem is an important observation for such frames.

######  Theorem IV.4.

For a given frame $\Phi,$ if the matrix formed by taking square of entries of
$\Phi$ is also a frame, then coherence remains unchanged by action of any
diagonal preconditioner that belongs to $S_{\Phi}$.

###### Proof.

Let us assume that $G=\mbox{diag}(\lambda^{G}_{1},\dots,\lambda^{G}_{m})\in
S_{\Phi}$, i.e., $G\Phi$ is a unit norm frame. It is clear that the standard
orthonormal vectors $\\{e_{j}\\}^{m}_{j=1}$ of $\mathbb{R}^{m}$ are the eigen
vectors of $G$ corresponding to eigen values
$\\{\lambda^{G}_{j}\\}^{m}_{j=1}.$ Then,
$\mathbb{R}(\Phi,\mathbb{E})=\mbox{span}\\{(|\left\langle\phi_{i},e^{G}_{j}\right\rangle|^{2})^{m}_{j=1}\\}^{M}_{i=1}=\mbox{span}\\{\phi^{2}_{i}\\}^{M}_{i=1},$
where $\phi^{2}_{i}=(\phi^{2}_{1i},\dots,\phi^{2}_{mi})^{T}.$ It is clear that
if $\mbox{span}\\{\phi^{2}_{i}\\}^{M}_{i=1}=\mathbb{R}^{m},$ then by Theorem
IV.1, $I_{m}$ is the only diagonal preconditioner that belongs to $S_{\Phi}$.
This completes the proof. ∎

Therefore, we can hope for improvement in coherence via a diagonal pre-
conditioner only when
$\mbox{span}\\{\phi^{2}_{i}\\}^{M}_{i=1}\neq\mathbb{R}^{m}$. In that case the
problem $C_{1}^{\prime}$ can be converted to a linear programming problem
(LPP) described below:

$\displaystyle\underset{\sigma_{1},\sigma_{2},\cdots,\sigma_{m},q}{\text{max}}$
$\displaystyle(-q)$ subject to
$\displaystyle\sum^{m}_{k=1}\sigma_{k}\phi_{ik}^{2}=1,\forall i=1,\dots,M;$
$\displaystyle-q\leq\sum^{m}_{k=1}\sigma_{k}\phi_{ik}\phi_{jk}\leq q,\forall
1\leq i<j\leq M;$ $\displaystyle\sigma_{k}\geq 0;\forall k=1,\dots,m;$
$\displaystyle q\geq 0$

Here, $\sigma_{k}$ acts as $(\lambda_{k}^{G})^{2}$. This formulation can be
solved by any existing interior point LPP solvers [39, 40] so that the
condition $\sigma_{k}>0$ is satisfied in every iteration.

######  Remark IV.5.

An implication of the previous theorem is that any frame with binary $0,1$
entries, constructed for example in [29, 30, 31, 32, 42]), does not allow for
fall in coherence value via diagonal pre-conditioning.

###  IV-C Semi-definite programming (SDP) for general preconditioners:

Adding slack and surplus variables $p_{ij}\geq 0$ and $q_{ij}\geq 0$, we
obtain the following equivalent formulation of $C_{1}^{\prime}$:

$C_{1}^{\prime\prime}:\begin{aligned}
&\underset{X,q,p_{ij},q_{ij}}{\text{max}}&&(-q)\\\ &\text{subject
to}&&\phi^{T}_{i}X\phi_{i}=1,\forall i=1,\dots,M;\\\
&&&\phi^{T}_{i}X\phi_{j}+p_{ij}-q=0,\forall 1\leq i<j\leq M;\\\
&&&-\phi^{T}_{i}X\phi_{j}+q_{ij}-q=0,\forall 1\leq i<j\leq M;\\\ &&&X\geq 0\\\
&&&q\geq 0\\\ &&&p_{ij}\geq 0,\forall 1\leq i<j\leq M;\\\ &&&q_{ij}\geq
0,\forall 1\leq i<j\leq M;\end{aligned}$

For the purpose of analysis later, we define the sets,
$D^{+}(X,q)=\\{(i,j):\phi^{T}_{i}X\phi_{j}=q\\}$ and
$D^{-}(X,q)=\\{(i,j):\phi^{T}_{i}X\phi_{j}=-q\\}.$ It is clear that $p_{ij}=0$
if $(i,j)\in D^{+}(X,q)$ and $q_{ij}=0$ if $(i,j)\in D^{-}(X,q)$. Let
$M^{\prime}=\frac{M(M-1)}{2}$ and $\mathbf{0}$ denote a zero matrix of size
$m\times m$, $\mathbf{0^{\prime}}$ a square zero matrix of size
$M^{\prime}\times M^{\prime}$, $P$ a diagonal matrix of size $M^{\prime}\times
M^{\prime}$ consisting of $p_{ij}$ as diagonal elements, $Q$ a diagonal matrix
of size $M^{\prime}\times M^{\prime}$ containing $q_{ij}$ as diagonal
elements, $\mathbf{1}_{ij}$ a diagonal matrix of size $M^{\prime}\times
M^{\prime}$ whose diagonal entries are indexed by arranging the tuples $(i,j)$
in lexicographic order for $1\leq i<j\leq M$ so that it contains $1$ at the
$(i,j)-$th diagonal element and zero elsewhere. For simplicity in notation, we
also let
$\phi^{\prime}_{ij}=\frac{\phi_{i}\phi_{j}^{T}+\phi_{j}\phi_{i}^{T}}{2}$ and
define the following block matrices.

$F_{0}=\begin{pmatrix}\mathbf{0}&0&0&0\\\ 0&\mathbf{0^{\prime}}&0&0\\\
0&0&\mathbf{0^{\prime}}&0\\\
0&0&0&1\end{pmatrix},\;F_{ii}=\begin{pmatrix}\phi_{i}\phi_{i}^{T}&0&0&0\\\
0&\mathbf{0^{\prime}}&0&0\\\ 0&0&\mathbf{0^{\prime}}&0\\\
0&0&0&0\end{pmatrix}$,

$F_{ij}=\begin{pmatrix}\phi^{\prime}_{ij}&0&0&0\\\ 0&\mathbf{1}_{ij}&0&0\\\
0&0&\mathbf{0^{\prime}}&0\\\
0&0&0&-1\end{pmatrix},\;Y=\begin{pmatrix}X&0&0&0\\\ 0&P&0&0\\\ 0&0&Q&0\\\
0&0&0&q\end{pmatrix}$,

$F_{ji}=\begin{pmatrix}-\phi^{\prime}_{ij}&0&0&0\\\
0&\mathbf{0^{\prime}}&0&0\\\ 0&0&\mathbf{1}_{ij}&0\\\ 0&0&0&-1\end{pmatrix}$.

It is easy to check that, for $1\leq i<j\leq M$, $F_{ii}$, $F_{ij},$ $F_{ji}$
and $F_{0}$ are symmetric. $C^{\prime\prime}_{1}$ can be formulated in a
standard SDP form [38] as

$SDP_{\mathbf{C}^{\prime\prime}_{1}}:\begin{aligned}
&\underset{Y}{\text{max}}&&-Tr(F_{0}Y)\\\ &\text{subject
to}&&Tr(F_{ii}Y)=1,\quad\forall\quad i=1,\dots,M;\\\
&&&Tr(F_{ij}Y)=0,\quad\forall\quad 1\leq i<j\leq M;\\\
&&&Tr(F_{ji}Y)=0,\quad\forall\quad 1\leq i<j\leq M,\\\ &&&Y\geq
0\end{aligned}$

The dual of $SDP_{\mathbf{C}^{\prime\prime}_{1}}$ is given by :

$SDPD_{\mathbf{C}^{\prime\prime}_{1}}:\begin{aligned}
&\underset{Z={\\{z_{ij}\\}}}{\text{min}}&&C^{T}_{M^{\prime\prime}}Z\\\
&\text{subject
to}&&F_{0}+\sum^{M}_{i=1}z_{ii}F_{ii}+\sum^{M}_{i,j=1,i<j}z_{ij}F_{ij}+\\\
&&&~{}~{}~{}\sum^{M}_{i,j=1,i<j}z_{ji}F_{ji}\geq\mathbf{0^{\prime\prime}}\end{aligned}$

where $\mathbf{0^{\prime\prime}}$ is a square zero matrix of size
$M^{\prime\prime}=M^{2}-M+m+1$ and $C_{M^{\prime\prime}}$ is a vector of
length $M^{\prime\prime}$ whose first $M$ elements are equal to one and rest
are zero. $SDP_{\mathbf{C}^{\prime\prime}_{1}}$ and
$SDPD_{\mathbf{C}^{\prime\prime}_{1}}$ can be solved by primal-dual path
following methods [38]. In this paper, the simulations are obtained using the
SDPT3 solver of CVX toolbox for MATLAB.

##  V Analysis of optimal solution

It is easy to check that, with $X$ being the identity matrix,
$p_{ij}=1-\phi_{i}^{T}\phi_{j},$ $q_{ij}=1+\phi_{i}^{T}\phi_{j}$ and $q=1$,
$Y$ becomes a strict feasible solution of
$SDP_{\mathbf{C}^{\prime\prime}_{1}}$. Similarly, it is easily verified that
with $z_{ii}=1$ and $z_{ij}=z_{ji}=\frac{1}{M^{2}}$, $Z$ becomes a strict
feasible solution of $SDPD_{\mathbf{C}^{\prime\prime}_{1}}$. Since both primal
and dual have strict feasible solutions, by Strong Duality Theorem [38],
optimal values of primal and dual coincide with each other. Consequently, the
duality gap is zero for any optimal pair $(Y^{*},Z^{*}),$ where $Y^{*}$ is an
optimal solution for $SDP_{\mathbf{C}^{\prime\prime}_{1}}$ and $Z^{*}$ is an
optimal solution for $SDPD_{\mathbf{C}^{\prime\prime}_{1}}.$ The duality gap
being zero implies that
$0=C^{T}_{M^{\prime\prime}}Z^{*}+Tr(F_{0}Y)=\sum^{M}_{i=1}z^{*}_{ii}+q^{*}$
which implies further that $q^{*}=-\sum^{M}_{i=1}z^{*}_{ii}.$

Now from the equation (33) of [38], the optimality condition

$\begin{split}Y^{*}&\left(F_{0}+\sum^{M}_{i=1}z^{*}_{ii}F_{ii}+\sum^{M}_{i,j=1,i<j}z^{*}_{ij}F_{ij}+\sum^{M}_{i,j=1,i<j}z^{*}_{ji}F_{ji}\right)\\\
&\quad=\mathbf{0^{\prime\prime}}.\end{split}$

gives

  1. (i)

$X^{*}\bigg{(}\sum^{M}_{i=1}z^{*}_{ii}\phi_{i}\phi^{T}_{i}+\sum^{M}_{i,j=1,i<j}(z^{*}_{ij}-z^{*}_{ji})\phi^{\prime}_{ij}\bigg{)}=0$

  2. (ii)

$z^{*}_{ij}p^{*}_{ij}=0$

  3. (iii)

$z^{*}_{ji}q^{*}_{ij}=0$

  4. (iv)

$q^{*}\left(1-\sum^{M}_{i,j=1,i<j}(z^{*}_{ij}+z^{*}_{ji})\right)=0$

If we assume that $X^{*}>0$, the first equality above reduces to

$\sum^{M}_{i=1}z^{*}_{ii}\phi_{i}\phi^{T}_{i}+\sum^{M}_{i,j=1,i<j}(z^{*}_{ij}-z^{*}_{ji})\phi^{\prime}_{ij}=0.$

From the definition of $D^{+}(X^{*},q^{*})$ and $D^{-}(X^{*},q^{*}),$ it
follows that $z^{*}_{ij}=0$ if $(i,j)\notin D^{+}(X^{*},q^{*})$ and
$z^{*}_{ji}=0$ if $(i,j)\notin D^{-}(X^{*},q^{*})$. As it is clear that
$q^{*}>0,$ for e.g. due to Welch bound, we have,

$\begin{split}1&=\sum^{M}_{i,j=1,i<j}(z^{*}_{ij}+z^{*}_{ji})\\\
&=\sum_{(i,j)\in D^{+}(X^{*},q^{*})}{z^{*}_{ij}}+\sum_{(i,j)\in
D^{-}(X^{*},q^{*})}{z^{*}_{ji}}.\end{split}$

######  Theorem V.1.

For a given unit norm frame $\Phi=\\{\phi_{i}\\}^{M}_{i=1},$ an invertible
matrix $\tilde{G}$ is a solution to $C_{1}^{{}^{\prime\prime}}$ if and only if
there exist scalars such that $\\{\tilde{z}_{ij}\\}^{M}_{i,j=1}$ such that the
following relations hold

  1. (i)

$\tilde{z}_{ij}=0$ for $(i,j)\notin
D^{+}(\tilde{G}^{T}\tilde{G},\mu_{\tilde{G}\Phi})$,

  2. (ii)

$\tilde{z}_{ji}=0$ for $(i,j)\notin
D^{-}(\tilde{G}^{T}\tilde{G},\mu_{\tilde{G}\Phi})$,

  3. (iii)

$\sum^{M}_{i,j=1,i<j}(\tilde{z}_{ij}+\tilde{z}_{ji})=1$,

  4. (iv)

$\sum^{M}_{i=1}\tilde{z}_{ii}\phi_{i}\phi^{T}_{i}+\sum^{M}_{i,j=1,i<j}(\tilde{z}_{ij}-\tilde{z}_{ji})\phi^{\prime}_{ij}=0.$

It can be noted here that once $D^{+}$ and $D^{-}$ are known, the above
conditions give rise to linear system of equations. We can now derive a
sufficient condition to obtain a pre-conditioner that reduces the initial
coherence.

######  Corollary V.2.

For a unit norm frame $\Phi$, the solution to $C_{1}^{{}^{\prime\prime}}$
results in strict decrease in coherence if and only if there do not exists
scalars $\\{\tilde{r}_{ij}\\}^{M}_{i,j=1}$ such that the following relations
hold true:

  1. (i)

$\tilde{r}_{ij}=0$ for $(i,j)\notin D^{+}(\mathbf{I}_{m},\mu_{\Phi})$,

  2. (ii)

$\tilde{r}_{ji}=0$ for $(i,j)\notin D^{-}(\mathbf{I}_{m},\mu_{\Phi})$,

  3. (iii)

$\sum^{M}_{i,j=1,i<j}(\tilde{r}_{ij}+\tilde{r}_{ji})=1$,

  4. (iv)

$\sum^{M}_{i=1}\tilde{r}_{ii}\phi_{i}\phi^{T}_{i}+\sum^{M}_{i,j=1,i<j}(\tilde{r}_{ij}-\tilde{r}_{ji})\phi^{\prime}_{ij}=0.$

###### Proof.

As there is a strict fall in coherence, $I_{m}$ is not a solution to
$C_{1}^{{}^{\prime\prime}}$. The result now follows from the previous theorem.
∎

The above conditions determine a linear system of equalities in the variables
$\tilde{r}_{ij}$. According to the corollary, the existence of a
preconditioner that results in a strict fall in coherence can be ascertained
by checking this system for infeasibility.

######  Remark V.3.

As ETFs already touch the Welch bound, the associated system of equalities in
$\tilde{r}_{ij}$ does not have a solution.

######  Remark V.4.

An important issue with the SDP formulation is that there is, in general, no
guarantee for the optimal solution $G$ to be non-singular. In practice,
however, the primal-dual interior point method described in [38] guarantees
the solution at every iteration is non-singular.

##  VI Preconditioner in the Noisy Case

Despite the fact that solving the two linear systems $\Phi x=y$ and $G\Phi
x=Gy$ is the same, the error produced by them can differ significantly in the
noisy case. i.e. $y=\Phi x+\eta$. The error relation of $\Phi x=y$ and $G\Phi
x=Gy$ can be expressed in the following way:

$\sigma_{\min}(G)\|\Phi x-y\|_{2}\leq\|G\Phi
x-Gy\|_{2}\leq\sigma_{\max}(G)\|\Phi x-y\|_{2},$

where $\sigma_{\min}(G)$ and $\sigma_{\max}(G)$ are minimum and maximum
singular values of matrix $G$ respectively. In the presence of noise it is
desirable that the condition number $\kappa{(G)}$ of the preconditioner $G$
remains small. Hence, the relationship between $\kappa{(G)}$ and $\mu(G\Phi)$
assumes importance. To understand the relationship between the condition
number of $G$ and the coherence of $G\Phi$, we introduce two new terms in the
convex optimization problem $C_{1}$. Since $\kappa(X)=\kappa(G)^{2},$ the
condition number $\kappa(G)$ of $G$ can be controlled by placing restriction
on the maximum and minimum eigenvalues of $X$, which is stated via the
following optimization problem:

$C_{2}:\begin{aligned} &\underset{X}{\text{min}}&&\max_{i\neq
j}|\phi^{T}_{i}X\phi_{j}|\\\ &\text{subject
to}&&\phi^{T}_{i}X\phi_{i}=1,\forall i=1,\dots,M\\\ &&&t_{2}I_{m}\leq X\leq
t_{1}I_{m},\\\ \end{aligned}$

where $t_{1}\geq t_{2}>0$. It can be noted that $C_{2}$ can also be recast as
a semi-definite program. As the details are similar to the formulation given
previously they are not repeated here. The bounds on $\lambda_{\mbox{max}}(X)$
and $\lambda_{\mbox{min}}(X)$ in $C_{2}$ imply that
$\kappa(X)\leq\frac{t_{1}}{t_{2}}$.

######  Remark VI.1.

It can also be noted that the condition for existence of an optimizer other
than the identity matrix follows exactly the same arguments given in Corollary
V.2. Hence, it is also possible to ascertain whether there exists a non-
trivial solution to $C_{2}$ by checking a linear system of equations for
infeasibility.

##  VII Experimental Results

In this section we present the numerical results of our proposed method and
compare our method to the construction given in [36].

We have carried out our numerical work on Gaussian random matrices
$\Phi\in\mathbb{R}^{m\times M}$. In simulations, we have fixed column size $M$
as 64 and varied row size $m$ from 1 to 63.

To begin with, by solving the convex optimization problem $C_{1}^{\prime}$, we
have obtained a positive definite matrix $X\in\mathbb{R}^{m\times m}.$ To
obtain the non-singular matrix $G$ from positive definite matrix $X$, we have
applied Cholesky decomposition on $X$ which results in an incoherent unit norm
frame $G\Phi.$ In Figure 1, the coherence of $\Phi$ (dashed line with circles)
and $G\Phi$ (dashed line with stars) depict that the improvement in coherence
becomes prominent as $m$ increases. The dotted line with diamond symbol in
Figure 1 is the Welch bound.

The recoverability of the sparse vector $x\in\mathbb{R}^{M}$ by using the
frames $G\Phi$ and $\Phi$ is examined through the well known Phase-diagram
analysis [6]. In Figure 2, the region below the line with stars (Phase-diagram
of $G\Phi$) indicates the recovery region of $G\Phi$ and the region below the
line with circles (Phase-diagram of $\Phi$) presents the recovery region of
$\Phi.$ Therefore, it is clear that $G\Phi$ has better recovery region than
$\Phi.$

After obtaining the optimal $G$ via $C_{1}^{\prime}$, we have calculated the
nearest $\frac{M}{m}-$tight frame ${G_{1}\Phi}$ of $\Phi$ [15]. In Figure 3,
the coherence of $G_{1}\Phi$ is given by the dash-dotted line with cross
marks. We have compared our proposed optimization with the iterative method
proposed in [36] which is termed as IUNTF. In Figure 3, the coherence of the
incoherent frame obtained via iterative method proposed in [36] is denoted by
dash-dotted line with upward triangle. From this figure, it is clear that our
proposed method works better for larger $m$ in constructing incoherent frames
than the iterative method proposed in [36].

The recoverability of a sparse vector $x\in\mathbb{R}^{M}$ by using the frames
$G_{1}\Phi$ and $\Phi$ is examined through Phase-diagram analysis. In Figure
4, the region below dash-dotted line with upward triangle (Phase-diagram of
$G_{1}\Phi$) indicates the recovery region of $G_{1}\Phi$ and the region below
the line with circles (Phase-diagram of $\Phi$) presents the recovery region
of $\Phi.$ Therefore it is clear that $G_{1}\Phi$ has a better recovery region
than $\Phi.$

With a view towards analyzing the condition number of preconditioner, we have
solved the convex optimization problem $C_{2}$ by considering the same
Gaussian random matrix $\Phi\in\mathbb{R}^{63\times 64}.$ In $C_{2}$, we have
fixed $t_{2}$ and varied $t_{1}$ to obtain a relationship between the
coherence of $G\Phi$ and condition number $\kappa{(G)}$ which is shown in
Figure 5. In simulations, we fixed $t_{2}=1$, started with $t_{1}=1$ and
gradually incremented $t_{1}$ by 0.5. Figure 5 suggests that the coherence of
$G\Phi$ decreases as $t_{1}$ increases. After certain stage the coherence of
$G\Phi$ remains unchanged despite change in $t_{1}$. This phenomenon is
expected as the coherence of $G\Phi$ touches its minimum values after some
iterations, which is described in $C_{1}$. Tables 1 and 2 describe a subset of
results obtained from the frame $\Phi\in\mathbb{R}^{m\times 64}$ for
increasing values of $m.$

The proposed method solves for $k=100$ iterations. The running times vary from
a few minutes $(m=1)$ to an over two days run $(m=63)$ for fixed column size
$M=64$ on a machine having 32 GB RAM and Intel Xeon processor with speed of
2.20 GHz using CVX in MATLAB.

Figure 1: Aspect ratio vs coherence of frames $G\Phi$ and $\Phi$ for different row sizes $m\in\\{1,\dots,63\\}$ for a fixed column size $M=64.$ In addition this plot includes the Welch bound for each frame $\Phi$. This plot demonstrates that proposed method provides better incoherence than its existing counterparts. Figure 2: Phase-transition curves for Gaussian sensing frame $\Phi\in\mathbb{R}^{m\times 64}$ where $m\in\\{1,\dots,63\\}$ and its scaled version $G\Phi$. For a give sparsity $s\in\\{1,\dots,m\\}$ the recovery occurs below the curves. This plot depicts better sparse recovery region for the frames generated by the proposed method $C_{1}^{\prime}$. Figure 3: Aspect ratio vs coherence of frames $G_{1}\Phi$ and $\Phi$ for different row sizes $m\in\\{1,\dots,63\\}$ for a fixed column size $M=64.$ In addition this plot includes the Welch bound for each frame $\Phi$. This plot demonstrates that the proposed method provides better incoherence than the initial frame. Figure 4: Phase-transition curves for Gaussian sensing frame $\Phi\in\mathbb{R}^{m\times 64}$ where $m\in\\{1,\dots,63\\}$ and its scaled version $G_{1}\Phi$. For a give sparsity $s\in\\{1,\dots,m\\}$ the recovery occurs below the curves. This plot depicts better sparse recovery region for the frames generated by the proposed method. Figure 5: In the plot, the x-axis indicates condition number of a matrix $G$ and the y-axis indicates coherence of the scaled frame $G\Phi.$ This plot demonstrates that, as condition number of a matrix $G$ increases the coherence of the scaled frame $G\Phi$ decreases. TABLE I: Average coherence for 100 iterations of the frames $\Phi$, $G\Phi$ for the frame $\Phi\in\mathbb{R}^{m\times 64}$ with increasing values of $m$. The Table also includes Welch bound (WB).  $m$ | $\mu(\Phi)$ | $\mu(G\Phi)$ | WB
---|---|---|---
6 | 0.9676 | 0.9676 | 0.3917
12 | 0.8454 | 0.7709 | 0.2623
18 | 0.7407 | 0.5071 | 0.2014
24 | 0.6646 | 0.3629 | 0.1627
30 | 0.6167 | 0.2757 | 0.1341
36 | 0.5563 | 0.2208 | 0.1111
42 | 0.5227 | 0.1769 | 0.0912
48 | 0.5021 | 0.1403 | 0.0727
54 | 0.4694 | 0.1110 | 0.0542
60 | 0.4463 | 0.0760 | 0.0325
63 | 0.4351 | 0.0529 | 0.0159
TABLE II: Average coherence for 100 iterations of the frames $\Phi$, $G_{1}\Phi$ and IUNTF [36] for the frame $\Phi\in\mathbb{R}^{m\times 49}$ with increasing values of $m$. $m$ | $\mu(\Phi)$ | $\mu(G_{1}\Phi)$ | $\mu(IUNTF)$
---|---|---|---
6 | 0.9676 | 0.9645 | 0.9860
12 | 0.8454 | 0.8429 | 0.8469
18 | 0.7407 | 0.7144 | 0.7090
24 | 0.6646 | 0.6167 | 0.5948
30 | 0.6167 | 0.5328 | 0.5026
36 | 0.5563 | 0.4537 | 0.4236
42 | 0.5227 | 0.3982 | 0.3671
48 | 0.5021 | 0.3537 | 0.3573
54 | 0.4694 | 0.3064 | 0.5096
60 | 0.4463 | 0.2766 | 0.7575
63 | 0.4351 | 0.2703 | 0.5547

##  VIII Conclusion

In this paper, we have studied the effect of preconditioning on sparse
recovery properties via frame theory and convex optimization. In particular,
we have formulated an optimization problem for improving the coherence of the
resulting matrix, which has been solved using techniques from semidefinite
programming. When the preconditoner is diagonal, we have obtained analytical
conditions for verifying the possibility of strict decrease in coherence.
While in the general case, we have provided an analysis of the optimal
solution which gives conditions under which strict decrease in coherence is
possible. As preconditioners with small condition numbers are desired in the
noisy cases, we have given another convex formulation enforcing this
constraint. Further, we have discussed the guarantees for strict decrease in
coherence in this case. Through simulation results, we have studied the
relation between condition number of the preconditioner and its coherence. We
have also demonstrated numerically that the proposed method works better than
the methods with similar objectives.

##  IX Acknowledgment:

The first author is thankful for the support (Ref No. 19-06/2011(i)EU-IV) that
he receives from UGC, Govt of India and the second author gratefully
acknowledges the support being received from MHRD, Govt. of India. The last
author is thankful to CSIR (No. 25(219)/13/EMR-II), Govt. of India, for its
support.

## References

  * [1] O. Christensen, “An Introduction to Frames and Riesz Bases," Boston, MA, USA: Birkhauser, 2003.
  * [2] J. Kovacevic and A. Chebira,“Life beyond bases: The advent of frames(Part I)," IEEE Signal Process. Mag., vol. 24, no. 4, pp. 86-104,Jul. 2007.
  * [3] 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.
  * [4] I. Daubechies, “Ten Lectures on Wavelets," Philadelphia, PA, USA: SIAM, 1992.
  * [5] T. Strohmer and R. W. Heath, “Grassmannian frames with applications to coding and communication," Appl. Comput. Harmon. Anal., vol. 14, no. 3, pp. 257-275, 2003.
  * [6] J. L. Massey and T. Mittelholzer, “Observed universality of phase transition in high dimensional geometry, with implications for modern data analysis and signal processing," Phil. Trans. R. Soc. A (2009) 367, 4273–4293.
  * [7] J. A. Tropp, “Greed is good: Algorithmic results for sparse approximation," IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2231-2242, Oct. 2004.
  * [8] P. Viswanath and V. Anantharam, “Optimal sequences and sum capacity of synchronous CDMA systems,"’ IEEE Trans. Inf. Theory, vol. 45, no. 6, pp. 1984-1991, Sep. 1999.
  * [9] P. Viswanath and V. Anantharam, “Optimal sequences for CDMA under colored noise: A Schur–Saddle function property," IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1295-1318, Jun. 2002.
  * [10] R. B. Holmes and V. I. Paulsen, “Optimal frames for erasures,"’ Linear Algebra Appl., vol. 377, no. 1, pp. 31-51, 2004.
  * [11] Y. C. Eldar and G. D. Forney, “Optimal tight frames and quantum measurement," IEEE Trans. Inf. Theory, vol. 48, no. 3, pp. 599-610, Mar. 2002.
  * [12] B. G. Bodmann and P. G. Casazza, “The road to equal-norm Parseval frames," J. Funct. Anal., vol. 258, no. 2, pp. 397-420, 2010.
  * [13] P. G. Casazza, M. Fickus, and D. G. Mixon, “Auto-tuning unit norm frames," Appl. Comput. Harmon. Anal., vol. 32, no. 1, pp. 1-15, 2012.
  * [14] M. Fickus, D. G. Mixon, and J. C. Tremain, “Steiner equiangular tight frames," Linear Algebra Appl., vol. 436, no. 5, pp. 1014-1027, 2012.
  * [15] P. G. Casazza and G. Kutyniok, eds., “Finite frames: Theory and applications", Birkh¨auser Boston, Inc., Boston, MA, 2012.
  * [16] J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, “Explicit constructions of RIP matrices and related problems," Duke Math. J. 159, 145-185, 2011.
  * [17] E. Candes, “The restricted isometry property and its implications for compressed sensing," Comptes Rendus Mathematique, Vol. 346, pp. 589-592, 2008.
  * [18] E. Candes, J. Romberg and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements," Comm. Pure and Appl. Math, 59, 1207-1223, 2006.
  * [19] E. Candes and T. Tao, “Decoding by linear programming," IEEE Trans. Inform. Theory 51, 42-4215, 2005.
  * [20] J. A. Tropp and S. J. Wright, “Computational methods for sparse solution of linear inverse problems," Proceedings of the IEEE, vol. 98, no. 6, pp.948-958, 2010.
  * [21] D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization", Proc. Natl. Acad. Sci. USA 100, No. 5: 2197 - 2202 (2003).
  * [22] J. A. Tropp, I. S. Dhillon, R. W. Heath Jr. and T. Strohmer, “Designing structured tight frames via an alternating projection method," IEEE Trans. Inf. Theory, vol. 51, no.1, pp. 188–209, 2005.
  * [23] M. Elad, “Optimized projections for compressed sensing," IEEE Trans. Signal Process., vol. 55, no. 12, pp. 5695-5702, Dec. 2007.
  * [24] E. J. Candes and T. Tao, “Near-optimal signal recovery from random projections: universal encoding strategies," IEEE Trans. Inform. Theory 52, no. 2, 489-509, 2006.
  * [25] S.S. Chen, D.L. Donoho and M.A. Saunders, “Atomic Decomposition by Basis Pursuit," SIAM, Review 43, 129-159, 2001.
  * [26] D. Donoho, “Compressed Sensing," IEEE Trans. Information Theory, 52, pp 1289-1306, 2006.
  * [27] D.L. Donoho, M. Elad and V.N. Temlyakov, “Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise," IEEE Trans. Inform. Theory 52, 6-18, 2006.
  * [28] Elad. M, “Sparse and Redundant Representations; from theory to applications in signal and image processing," Springer, Berlin, 2010.
  * [29] Ronald A. DeVore, “Deterministic constructions of compressed sensing matrices," Journal of Complexity, Volume 23,pp 918-925, 2007.
  * [30] S.Li and G. Ge, “Deterministic Construction of Sparse Sensing Matrices via Finite Geometry," IEEE Transactions on Signal Processing ,Volume 62, Issue 11, June1, 2014.
  * [31] S. Li, F. Gao, G. Ge, and S. Zhang, “Deterministic construction of compressed sensing matrices via algebraic curves," IEEE Trans. Inf. Theory, vol. 58, 5035-5041, 2012.
  * [32] A. Amini and F. Marvasti, “Deterministic construction of binary, bipolar and ternary compressed sensing matrices," IEEE Trans. Inf. Theory, vol. 57, 2360-2370, 2011.
  * [33] C Rusu and N. G. Prelcic “Designing Incoherent Frames Through Convex Techniques for Optimized Compressed Sensing," IEEE Transactions on Signal Processing 64(9):1-1 · May 2016.
  * [34] C Rusu, “Design of Incoherent Frames via Convex Optimization," IEEE Signal Processing Letters, VOL. 20, NO. 7, 2013.
  * [35] E. Tsiligianni, L. P. Kondi, A. K. Katsaggelos, “Construction of Incoherent Unit Norm Tight Frames With Application to Compressed Sensing," IEEE Transactions on Information Theory, VOL. 60, NO. 4, 2014
  * [36] E. Tsiligianni, L. P. Kondi, A. K. Katsaggelos, “Preconditioning for Underdetermined Linear Systems with Sparse Solutions," IEEE Signal Processing Letters, Vol. 22, No. 9, 2015.
  * [37] J. Cahill, P. G. Casazza and G. Kutyniok, “Operators and frames," Journal of Operator Theory, Volume 70, Issue 1, Summer 2013 pp. 145-164.
  * [38] L. Vandenberghe and S. Boyd, “Semidefinite Programming," SIAM Review, Vol. 38, No. 1, pp. 49-95, March 1996.
  * [39] M. Grant, S. Boyd, and Y. Ye., “Disciplined Convex Programming", in L. Liberti and N. Maculan, eds., Global Optimization: From Theory to Implementation, Springer, chapter 7, pp.155-210, 2006.
  * [40] C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz, “An Interior point method for semidefinite programming", J. Optimization, SIAM Vol. 6, No. 2, pp. 342-361, May 1996.
  * [41] B.S. Kashin and V.N. Temlyakov, “A remark on compressed sensing," Matematicheskie Zametki, Vol. 82, No. 6, pp. 829–837, 2007.
  * [42] R. R. Naidu, P. Jampana, C. S. Sastry, “Deterministic Compressed Sensing Matrices: Construction via Euler Squares and Applications," IEEE Transactions on Signal Processing 64(14), 2016.