# Achieving Low Latency at Low Outage:
Multilevel Coding for mmWave Channels ††thanks: The research at UCLA was
supported in part by the U.S. National Science Foundation (NSF) under grant
no. ECCS-2229560. The work of M. Cardone was supported in part by the NSF
under grant no. CCF-2045237. This material is also based upon work supported
by the NSF under grant no. CNS-2146838 and is supported in part by funds from
federal agency and industry partners as specified in the Resilient &
Intelligent NextG Systems (RINGS) program.

Mine Gokce Dogan1, Jaimin Shah2, Martina Cardone2, Christina Fragouli1,
Wei Mao3, Hosein Nikopour3, and Rath Vannithamby3  1University of California,
Los Angeles Los Angeles, CA 90095, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>2University of Minnesota, Minneapolis, MN 55455,
{shah0732<EMAIL_ADDRESS>3Intel Corporation, Santa Clara, CA 95054
{wei.mao, hosein.nikopour<EMAIL_ADDRESS>
###### Abstract

Millimeter-wave (mmWave) spectrum is expected to support data-intensive
applications that require ultra-reliable low-latency communications (URLLC).
However, mmWave links are highly sensitive to blockage, which may lead to
disruptions in the communication. Traditional techniques that build resilience
against such blockages (among which are interleaving and feedback mechanisms)
incur delays that are too large to effectively support URLLC. This calls for
novel techniques that ensure resilient URLLC. In this paper, we propose to
deploy multilevel codes over space and over time. These codes offer several
benefits, such as they allow to control what information is received and they
provide different reliability guarantees for different information streams
based on their priority. We also show that deploying these codes leads to
attractive trade-offs between rate, delay, and outage probability. A
practically-relevant aspect of the proposed technique is that it offers
resilience while incurring a low operational complexity.

##  I Introduction

Next generation wireless networks are expected to support a wide range of
data-intensive applications that require ultra-reliable low-latency
communications (URLLC). Examples include cloud gaming and live stream
$360^{\circ}$ virtual reality. These applications impose strict Quality of
Service (QoS) requirements: packet delay budgets of $50$ ms, packet error
rates of $10^{-3}$, and data rates up to $80$ Mbps [1]. URLLC are also
required for mission-critical applications, such as autonomous driving,
factory automation, and remote surgery.

A key enabling technology that can support the URLLC use cases leverages the
millimeter-wave (mmWave) spectrum. Despite this promising aspect of mmWave
communications, it is well known that mmWave links are highly sensitive to
blockage and communication can get disrupted. Traditional techniques that
offer resilience against blockages use interleaving and feedback mechanisms.
However, these come at the cost of low information rate, increased latency, or
low reliability.

In this paper, we propose to deploy multilevel codes [2, 3] for resilient
URLLC. In particular, we encode the source sequences in packets and send them
over multiple network paths (that may exist between a source and a
destination) and over multiple time slots. We do this by assuming the
knowledge of the link blockage probabilities. These probabilities can be
estimated through accurate models in advance [4, 5, 6, 7]. Our proposed
transmission schemes have the following advantages.

First, they are proactive, i.e., they build resilience in advance without an a
priori knowledge of the blockages. This ensures communication guarantees with
no additional delay, even if blockages diminish network resources. Thus,
proactive mechanisms are suitable for delay-sensitive applications which may
require latency as low as a few milliseconds [1].

Second, multilevel codes allow to control what information is received even if
only a subset of the paths are available to operate. This is a challenging
task because once a blocker interrupts a communication link, it causes that
link to become unavailable for a certain duration. Thus, only a subset of the
paths might be available while operating the network, and we do not know in
advance which ones. We cannot simply “average out” these events while
providing reliability and latency guarantees for delay-sensitive applications.
For example, consider a network with $6$ paths, all with blockage probability
$0.3$. Assume that once a blocker interrupts a path, it continues to interrupt
that path for $500$ ms. When this network starts to operate, any $2$ paths can
get blocked with probability $0.32$. That means, only $4$ of the paths (and we
do not know which ones) can be operational for $500$ ms. If we simply send
uncoded data, we cannot control the received information when some paths are
operational for a certain duration111If we send $6$ independent information
streams, one through each path, we will have no control on which information
stream will be received..

Third, multilevel codes offer different reliability guarantees to different
information streams based on their priority. This is particularly important
for data-intensive applications, in which more relevant information streams
need to be received with a higher probability and/or a lower latency, and/or
higher rate.

Fourth, multilevel codes do not have a single threshold of failure. They
provide a graceful performance degradation: if less than the expected amount
of blockages occur, we can leverage this to increase the information rate; and
if more blockages occur, the information rate will gradually decrease.

The aforementioned advantages come with a certain challenge: the operational
complexity of multilevel codes increases with the number of paths utilized and
the code duration.

Related Work. Several works in the literature offer resilience against link
outages by taking reactive approaches [8, 9, 10]. However, such reactive
mechanisms add the feedback latency and the complexity of identification and
adaptation. Several works proposed proactive approaches for resilience [11,
12], but they are different from our work as we propose coding schemes to
control what information is received, and to accommodate different reliability
requirements of different information streams. In [13], the authors proposed
low-complexity proactive mechanisms for mmWave networks by deploying
multilevel codes over space (i.e., across multiple paths). The authors then
extended this work to scenarios in which the path blockage probabilities are
unequal [14]. These works are different from our work as: (i) the operation of
their schemes relies on a multipath environment, which is not always
practical; and (ii) they focus on the rate-outage probability trade-off
without any delay requirements. On the contrary, in this paper: (i) we propose
to deploy multilevel codes both over space and time, which allows to deploy
them in networks that do not support a multipath environment; (ii) we consider
time correlation of blockages; and (iii) we consider the trade-off between the
rate, delay, and outage probability. The extended version of the Related Work
is delegated to Appendix A.

Contributions and Paper Organization. In Section II, we provide an overview on
the 1-2-1 model, on the erasure codes, and on the symmetric multilevel codes.
In Section III, we analyze the channel under the considered blockage model. In
particular, we derive the probability mass function (PMF) of the number of
received packets, and we further analyze this distribution. In Section IV, we
propose proactive transmission mechanisms for mmWave networks. In particular,
we propose to deploy symmetric multilevel codes over space and time. Towards
achieving an attractive trade-off between the rate and a graceful performance
degradation, we propose an optimization formulation to choose our design
parameters. We also present a low-complexity coding scheme that aims at
approximating well the aforementioned trade-off. In Section V, we numerically
evaluate the performance of our schemes and compare them with an alternative
scheme. In particular, we investigate the trade-off between the rate, delay,
and outage probability. Our evaluations show that: (i) the proposed schemes
achieve a more attractive trade-off between the rate, delay, and outage
probability by providing a more graceful performance degradation compared to
the alternative scheme; and (ii) our complexity reduction technique gives a
comparable performance, while significantly reducing the code complexity.
Finally, in Section VI we conclude the paper.

##  II System Model and Background

Notation. $[a\\!:\\!b]$ is the set of integers from $a$ to $b>a$, and
$|\cdot|$ is the cardinality for sets; $*$ denotes the convolution operation.
For a vector $v$, we denote with $\|v\|$ the $\ell_{2}$-norm of $v$.

We build on the 1-2-1 network model, which was introduced to study the
information-theoretic capacity of mmWave networks [15]. The model abstracts
away the physical layer component and focuses on modeling the directivity
characteristic of mmWave communications: mmWave nodes perform beamforming with
narrow beams to compensate the path loss.

We consider a 1-2-1 network with $N$ relays that assist the communication
between the source (node $0$) and the destination (node $N\\!+\\!1$). The
relays can operate either in full-duplex or half-duplex mode. Two nodes steer
their beams towards each other to activate a link that connects them (called a
1-2-1 link [15]). At any given time, the source and the destination can steer
their beams towards $H$ nodes ($H$ denotes the number of edge-disjoint paths
in the network), whereas the relays can transmit to (and receive from) at most
another node222Our results hold even if relays have multiple transmit and
receive beams..

Link Blockage Probabilities. We build on the existence of accurate models that
estimate the link blockage probabilities in mmWave networks [4, 5, 6, 7].
These works model the blocker arrival process as a Poisson point process
(PPP). In particular, the intensity $\alpha_{j,i}$ of the Poisson process for
the link from node $i\in[0\\!:\\!N]$ to node $j\in[1\\!:\\!N{+}1]$ is
$\alpha_{j,i}=\lambda_{j,i}d_{j,i}$, where: (i) $\lambda_{j,i}$ is
proportional to the blocker density and velocity, and to the heights of the
blockers, the receiver and the transmitter [4]; and (ii) $d_{j,i}$ is the
distance between nodes $i$ and $j$.

Figure 1: Blockage model illustration over a single LoS link.

Similarly, in this paper we assume a PPP for the blocker arrivals. If a
blocker interrupts a line-of-sight (LoS) link, it continues to interrupt that
link for the consecutive $L$ time slots, where $L$ is a constant value. In
this work, we assume uncorrelated blockages across different links. In Fig. 1,
we illustrate our blockage model for a single link. We allow for overlaps of
blockages as shown in Fig. 1. That is, if a blocker interrupts a link, in the
meantime another blocker can start to interrupt the same link. This increases
the total blockage duration as shown with a red block in Fig. 1.

Erasure Codes. An erasure code is a forward error correction code that assumes
packet erasures (losses) [16, 17]. An erasure code $(n,k)$ transforms $k$
information packets into $n$ encoded packets such that the original message is
reconstructed if any $k$ packets (out of the $n$ transmitted packets) are
received. This results in an information rate of $k/n$. An erasure code
supports a given number of blockages: we experience “outage” if the number of
blockages is higher than the design (less than $k$ packets are received,
resulting in a zero information rate); and we succeed if there are fewer
blockages than the design (at least $k$ packets are received, resulting in an
information rate of $k/n$). Thus, erasure codes do not offer a graceful
performance degradation. Moreover, even if we succeed, experiencing fewer
blockages does not increase the information rate.

Multilevel Diversity Coding (MDC). MDC is a classical coding scheme that
provides a graceful performance degradation. It encodes i.i.d. source
sequences to accommodate different reliability requirements of different
source sequences. MDC can be designed in two ways: symmetric and asymmetric.
In this paper, we build our schemes on symmetric MDC.

In symmetric MDC [2, 3], $H$ i.i.d. source sequences are considered. They have
certain levels of importance, ordered from $1$ (the most important) to $H$
(the least important). They are encoded into $H$ descriptions using $H$
encoders. These descriptions are sent to $H$ decoders, each through a
different channel. There are $H$ levels and the decoders are assigned with
ordered levels. Each decoder has access to a subset of the descriptions, and
its level depends on the number of descriptions to which it has access. The
encoders produce the descriptions such that a decoder at level $h$ (i.e., has
$h$ available descriptions) can reconstruct the $h$ most important source
sequences, $h\in[1\\!:\\!H]$. For symmetric MDC, superposition coding is
optimal [2, 3]. That is, each source sequence is encoded separately, and the
descriptions are created by concatenating the encoded sequences appropriately.
The next example illustrates the $3$-level MDC and its potential benefits.

Example 1. Consider the network in Fig. 2 that has $H=3$ edge-disjoint paths
connecting the source (node $0$) to the destination (node $4$).

Figure 2: An example network with $N=3$ relays.

We let $U_{i},i\in[1\\!:\\!3]$ be the i.i.d. source sequences, ordered with
decreasing importance. They are encoded by $H=3$ encoders, and each
description (denoted by $E_{i},i\in[1\\!:\\!3]$) is sent through a different
path. In Fig. 3, we show the setting of a $3$-level symmetric multilevel code
over this network.

Figure 3: $3$-level symmetric multilevel code setting.

The goal is to reconstruct $U_{i},i\in[1\\!:\\!h],$ if any $h$ paths succeed
(or equivalently, any $H-h$ paths fail). $\square$

Performance Metrics. We assess the proposed coding schemes performance through
the performance metrics below.

1) Outage Probability. As discussed, a single erasure code can support only up
to a certain number of packet losses. For a higher number of packet losses,
the network experiences outage. The probability of outage is defined as
follows.

###### Definition 1

The outage probability of an erasure code $(n,k)$ is defined as,

$\displaystyle P_{\rm{out}}=P(X<k),$ (1)

where the random variable $X$ denotes the total number of packets received by
the destination. $\square$

As we discuss in Section IV, multilevel codes can be designed by combining
multiple erasure codes. Thus, they do not have a single outage probability:
there is a different outage probability for every erasure code combined by the
multilevel code.

2) Average Rate. Our second performance metric is the average information rate
of an erasure code.

###### Definition 2

The average information rate of an erasure code $(n,k)$ is defined as,

$\displaystyle R_{\rm{E,(n,k)}}=\frac{k}{n}\left(1-P_{\rm{out}}\right),$ (2)

where $P_{\rm{out}}$ is the outage probability in Definition 1. $\square$

Since a multilevel code can be designed by combining multiple erasure codes
(see Section IV), its average rate is equal to a weighted sum of the average
rates of the erasure codes that are combined. It is formally presented in
Definition 3.

3) Delay. The final performance metric is the delay, which quantifies the
amount of time needed to transmit the source sequences. As we discuss in
Section IV, we propose to deploy the coding schemes over time: we first encode
the source sequences and then transmit the encoded sequences over $T$ time
slots, where $T$ denotes the code duration. We assume that each time slot
lasts for one transmission time interval (TTI) denoted by $t_{d}$ (e.g.,
$t_{d}=250~{}\mu$s [18]). Thus, the delay of every coding scheme considered in
this paper is equal to $Tt_{d}$. We choose the value of $T$ according to the
latency constraints.

##  III Channel Analysis

In this section, we analyze the channel, and we derive the PMF of the number
of received packets.

We consider a 1-2-1 network with $H$ edge-disjoint paths. As we discuss in
Section IV, we encode the source sequences in packets and transmit the packets
over $T$ time slots. Each time slot $t_{k}$, $k\in[1\\!:\\!T]$ lasts for one
TTI. The blocker arrival process on path $p_{j}$ is a PPP with intensity
$\alpha_{j}$ per TTI for $j\in[1\\!:\\!H]$. Thus, the number of blockers that
interrupt path $p_{j}$ at time slot $t_{k}$, $k\in[1\\!:\\!T]$ has a Poisson
distribution with parameter $\alpha_{j}$. Since the PPP has independent
increments and each time slot is a disjoint interval in time, a new blockage
event can independently start on path $p_{j}$ (i.e., at least one new blocker
interrupts the path) at every time slot with probability,

$\varepsilon_{j}=1-{\rm{e}}^{-\alpha_{j}},~{}j\in[1:H].$ (3)

As discussed in Section II, once a blocker interrupts a path, it continues to
interrupt the path for $L$ time slots. In the rest of this paper, we assume
that blockage events can occur only at the beginning of a time slot. This
implies that an entire packet is either received or lost; we cannot receive a
partial packet.

Let $X$ denote the total number of received packets over $H$ paths through $T$
time slots. We have $X=\sum_{j=1}^{H}X_{j}$ where $X_{j}$ denotes the number
of received packets on path $p_{j}$ over $T$ time slots, for $j\in[1:H]$. Thus
the PMF of $X$, denoted by $P_{X}$, can be written as,

$P_{X}=P_{X_{1}}*\ldots*P_{X_{H}},$ (4)

where $P_{X_{j}}$ is the PMF of $X_{j}$, $j\in[1\\!:\\!H]$ and it is derived
in the following proposition (proof in Appendix B).

###### Proposition 1

Consider a 1-2-1 network with $H$ edge-disjoint paths. Let $T$ denote the code
duration and $L$ denote the blockage duration in time slots, such that $L\geq
T$. Then, $P_{X_{j}}$, $j\in[1:H]$ is given by:

$\bullet$ The probability $P_{X_{j}}(0)=P(X_{j}=0)$ is

$P_{X_{j}}(0)=\varepsilon_{j}+\sum_{i=1}^{T}(1-\varepsilon_{j})^{i}\varepsilon_{j}^{\min\\{T-i,1\\}}\left(1-(1-\varepsilon_{j})^{L-i}\right),$

where $\varepsilon_{j}$ is defined in (3).

$\bullet$ For $0<r\leq T$, the probability $P_{X_{j}}(r)=P(X_{j}=r)$ is

$P_{X_{j}}(r)\\!=\\!\sum_{i=0}^{T-r}(1\\!-\\!\varepsilon_{j})^{r+i}\varepsilon_{j}^{\min\\{T-r-i,1\\}}(1\\!-\\!\varepsilon_{j})^{L-1-i}\varepsilon_{j}^{\min\\{i,1\\}}.$

###### Remark 1

It is reasonable to assume $L\\!\geq\\!T$ in practice. First, the value of $T$
is constrained by the latency requirements of delay-sensitive applications (at
most $100$ ms latency [1]). The delay of every coding scheme considered in
this paper is $Tt_{d}$ as discussed in Section II, thus we constrain the value
of $T$ (e.g., $T\leq 400$ for $t_{d}=250~{}\mu$s). Second, measurement studies
show that the blockage duration is of the order of $100$ ms [4, 5, 6, 7]. In
this work, the blockage duration due to a single blocker is
$Lt_{d}$333Overlapping blockage events can extend the total blockage duration
but the blocked intervals are likely to feature a single blocker occluding the
path [5].. For example, this requires $L\geq 400$ for $t_{d}=250~{}\mu$s.

We next show a property of the number of received packets (see Appendix C for
the detailed proof).

###### Proposition 2

If (i) $\varepsilon_{j}(T-1)\ll 1$, or (ii) $(1-\varepsilon_{j})^{L}\ll 1$ and
$\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}\ll 1$, the following
approximation holds for $j\in[1\\!:\\!H]$,

$P_{X_{j}}(0)+P_{X_{j}}(T)\approx 1.$ (5)

Moreover, it always holds that $\lim_{L\to\infty}P_{X_{j}}(0)=1$.

In practice, the conditions in Proposition 2 may hold. First, as pointed out
in Remark 1, latency requirements constrain the value of $T$, and $L$ may take
large values as supported by measurement studies. Second, mmWave networks can
support short TTI durations, thus it is reasonable to assume that
$\varepsilon_{j}$ does not take large values. If the approximation in (5)
holds, the number of received packets on each path is likely to be either $0$
or $T$ at every $T$ time slots. That means, an uncoded transmission performs
well for $H\\!=\\!1$. However, if the approximation in (5) does not hold or if
$H>1$, the number of received packets takes different values. Assume the
approximation in (5) holds and $H>1$, then the number of received packets is
likely to take values $jT$ for $j\in[0\\!:\\!H]$ (see Appendix D for numerical
analysis). In all such cases, MDC provides a graceful performance degradation.

##  IV Proposed Coding Schemes

In this section, we discuss how to deploy multilevel codes. Our coding schemes
are largely based on the schemes proposed in [13]; however, different from
those in [13], they can also be deployed over time. This allows to reap their
benefits also in networks that do not support a multipath environment, and
allows to consider correlated blockages over time.

We let $H$ denote the number of edge-disjoint paths in the network and
$p_{[1:H]}$ is the corresponding set of edge-disjoint paths. We propose to
deploy symmetric multilevel codes over paths $p_{[1:H]}$ and over $T$ time
slots ($T$ denotes the code duration). Our scheme builds on superposition
coding discussed in Section II. We consider $HT$ i.i.d. source sequences
denoted by $U_{1},\ldots,U_{HT}$, which are ordered with decreasing
importance. We propose to encode each source sequence $U_{i}$ with a different
rate erasure code $(HT,i)$, $i\in[1\\!:\\!HT]$. We then concatenate the
encoded sequences to create combined packets denoted by $x_{j}^{(k)}$,
$j\in[1\\!:\\!H]$, $k\in[1\\!:\\!T]$. We transmit $x_{j}^{(k)}$ through path
$p_{j}\in p_{[1:H]}$ at time slot $t_{k}$444As discussed in Section II, every
combined packet is transmitted during one TTI (denoted by $t_{d}$) and the
transmission duration of $HT$ combined packets is $Tt_{d}$.. Every
$x_{j}^{(k)}$ consists of $HT$ components, and each component is created based
on a different rate erasure code. We use codes $(HT,i)$, $i\in[1\\!:\\!HT]$ to
create the components. Let $x_{j,i}^{(k)}$, $i\in[1\\!:\\!HT]$ denote the
components of $x_{j}^{(k)}$. Each $x_{j,i}^{(k)}$ is created based on a code
$(HT,i)$. We allocate a packet fraction to each code while creating the
combined packets: $f_{i}$ denotes the fraction of a combined packet allocated
to code $(HT,i)$, $i\in[1\\!:\\!HT]$. In Fig. 4, we illustrate our scheme for
$H=2$ and $T=3$. In what follows, we refer to the combined packets as packets.

Figure 4: Symmetric multilevel code design for $H\\!=\\!2$ and $T\\!=\\!3$.

Our scheme guarantees higher reliability to more important source sequences.
For example in Fig. 4, the most important source sequence $U_{1}$ is encoded
with the most reliable code $(6,1)$ (i.e., has the smallest outage
probability). Thus, $U_{1}$ is successfully decoded if at least one packet is
received. Under this scheme, if $r$ packets are received (out of the $HT$
transmitted packets) for $r\in[1\\!:\\!HT]$, the information rate is equal to
$\sum_{i=1}^{r}(i/HT)f_{i}$. The average information rate $R_{\mathrm{MC}}$ is
defined similarly, where MC refers to this proposed scheme.

###### Definition 3

The average information rate $R_{\mathrm{MC}}$ of a symmetric multilevel code
is,

$R_{\mathrm{MC}}=\sum_{i\in[1:HT]}\left(f_{i}P(X\geq i)\frac{i}{HT}\right),$
(6)

where $X$ denotes the number of received packets out of the transmitted $HT$
packets.

###### Remark 2

The average information rate $R_{\mathrm{MC}}$ in (6) is equal to a weighted
sum of average rates of erasure codes as defined in (2). The weights are the
packets fractions $f_{i}$, $i\in[1:HT]$.

###  IV-A Selection of the Packet Fractions

We propose the following optimization problem, which can be solved with off-
the-shelf solvers, to select the packet fractions $f_{i}$, $i\in[1:HT]$,

$\displaystyle\begin{array}[]{llll}&\underset{f}{\max}\
\sum_{i\in[1:HT]}\left(\frac{i}{HT}P(X\geq i)f_{i}\right)-\mu\lVert
f\rVert^{2}&\\\ &{\text{subject to}}\ \sum_{i\in[1:HT]}f_{i}=1,\\\
&{\text{and}}\ \ \ \ \ \ \ \ f\geq 0,\end{array}$ (10)

where: (i) $f$ denotes the vector of the packet fractions $f_{i}$,
$i\in[1\\!:\\!HT]$; and (ii) $\mu$ is a nonnegative trade-off parameter given
as input. The probability $P(X\geq i)$ in (10) can be computed through
Proposition 1. The problem in (10) aims to: (i) maximize the average
information rate of MC; and (ii) offer a graceful performance degradation. For
$\mu=0$, the objective function reduces to $R_{\mathrm{MC}}$ in (6). In this
case, due to the constraints in (10), an optimal solution will select (i.e.,
assign a nonzero packet fraction) a single erasure code that has the highest
average rate. However, this solution does not offer a graceful performance
degradation. As $\mu$ increases, an optimal solution allocates nonzero values
to a higher number of packet fractions to decrease the $\ell_{2}$-norm of $f$.
This offers a more graceful performance degradation at the cost of achieving a
lower average rate. Thus, there is a trade-off between two objectives and
there is no unique optimal solution. The parameter $\mu$ can be tuned
according to application requirements.

###  IV-B Low-complexity Coding Scheme

As our scheme combines $HT$ erasure codes, the code complexity increases as
$HT$ increases. We propose to reduce the complexity by selecting only $m<HT$
erasure codes. These codes can be selected according to application
requirements; here we select them by leveraging our results in Section III. If
the approximation in (5) holds, the number of received packets at every $T$
time slots is likely to be $jT$ for $j\in[0\\!:\\!H]$; thus, we can select
$m=H$ erasure codes $(HT,jT)$, $j\in[1\\!:\\!H]$ (or a subset of them to
decrease $m$ further). We then combine only the selected codes in our design.
The packet fractions of these $m$ erasure codes can be selected by solving
(10). In what follows, we will refer to this heuristic as MC-RC.

(a) $T=200$ and $L=400$.

(b) $L=400$.

(c) $L=400$.

Figure 5: Performance of the coding schemes over the network in Fig. 2 with
$H=3$ edge-disjoint paths.

##  V Performance Evaluation

In this section, we assess the performance of our schemes MC and MC-RC with
respect to the average information rate, delay, and outage probability. We
compare their performance with an alternative scheme, erasure code-reduced
outage (EC-RO). EC-RO encodes the source sequences over paths $p_{[1:H]}$ and
over $T$ time slots by using a single erasure code. The code is selected such
that the outage probability in (1) is not larger than a given threshold
$\gamma$. If there are multiple erasure codes that satisfy this condition, EC-
RO selects the code that has the highest information rate among them. The
information rate of the selected code is denoted by $R_{\text{EC-RO}}$. If all
erasure codes have an outage probability greater than $\gamma$, EC-RO selects
the code $(HT,1)$, which has the smallest outage probability.

We deploy MC, MC-RC, and EC-RO over the network in Fig. 2. Our coding schemes
can be applied to networks with arbitrary topologies by selecting edge-
disjoint paths among all paths. Thus, it can be assumed that the paths in Fig.
2 are selected from a larger network with an arbitrary topology.

We start with the rate and outage probability trade-off. We assume $T=200$ and
TTI duration $t_{d}=250~{}\mu$s [18], thus the transmission delay of $HT=600$
packets is $Tt_{d}=50$ ms for each scheme. For $L=400$, the blockage duration
due to a single blocker555Overlapping blockage events extend the total
blockage duration. is $Lt_{d}=100$ ms. The blocker arrival process on each
path is a PPP with intensity666That is, $\alpha_{j}=7.5\times 10^{-4}$
blockers per TTI, $j\in[1\\!:\\!H]$ in (3). $3$ blockers per second. We have
source sequences with different priorities and we require that the most
important source sequence has to be decoded with a high probability of at
least $0.995$. Additionally, we require that it is decoded at least at
information rate $R$. We accommodate these requirements by selecting
$\gamma=0.005$ for EC-RO. EC-RO selects an erasure code $(600,21)$. It
achieves rate $R_{\text{EC-RO}}=0.035$ whenever at least $21$ packets are
received. We select $R=0.1R_{\text{EC-RO}}$ in this experiment, so that we can
support the rate $R$ with $0.005$ outage probability. Similarly, we design MC
and MC-RC such that the most important source sequence can be decoded at least
at information rate $R$ with $P_{\rm{out}}\leq\gamma$. We do this by ensuring
that both MC and MC-RC select $f_{21}\geq R/R_{\text{EC-RO}}$ in (10)777This
can be achieved by adding an additional constraint to (10).. In Fig. 5(a), we
show the information rate achieved by our schemes versus the outage
probability (i.e., the probability that the scheme does not achieve that
rate). In Fig. 5(a), both MC and MC-RC can decode the most important source
sequence at rate $R$ with probability $0.995$ (i.e., $0.005$ outage
probability). They can decode additional source sequences at higher rates at
the cost of having a higher outage probability for them, e.g., MC-RC can
decode at least the three most important source sequences at rate $0.50$ with
probability $0.74$ (i.e., $0.26$ outage probability). We note that MC-RC
combines only $m=4$ erasure codes while MC combines $52$ codes. We also note
that EC-RO does not provide different reliability guarantees, and hence it
does not exhibit a graceful performance degradation: it either decodes all
sequences at rate $R_{\text{EC-RO}}=0.035$, or it fails to decode any of them
with probability $0.005$. Thus, a single erasure code only gives a single QoS
point, while multilevel codes give a series of points that can suit different
QoS requirements of different data streams.

We next evaluate the average information rate and delay trade-off. In Fig.
5(b), we show how the average rate changes as $T$ increases from $40$ to $400$
(i.e., delay increases from $10$ ms to $100$ ms). We find the average rate
over the simulated blockage realizations for the network in Fig. 2 and over
$10^{8}$ time slots. The blocker arrival process on each path is a PPP with
intensity888That is, $\alpha_{j}=7.5\times 10^{-4}$ blockers per TTI,
$j\in[1\\!:\\!H]$ in (3). $3$ blockers per second. All schemes encode and
transmit source sequences over $p_{[1:H]}$ paths at every $T$ time slots. In
Fig. 5(b), we average over the rates achieved at every $T$ time slots999The
achieved information rate depends on the number of received packets over $T$
time slots, on the selected erasure codes, and on the packet fractions.. For
every $T$, EC-RO aims at selecting an erasure code for $\gamma=0.005$.
Similarly, both MC and MC-RC are designed for $\gamma=0.005$ and
$R=0.1R_{\text{EC-RO}}$. In Fig. 5(b), the average rate of EC-RO decreases
until $T=120$ because all erasure codes have outage probability larger than
$\gamma$ until $T=120$ and thus, the code $(HT,1)$ is selected by EC-RO. For
higher values of $T$, EC-RO selects codes with $P_{\rm{out}}\leq\gamma$.
Moreover, outage probabilities of low-rate codes decrease as $T$ increases,
which increases their average rates. Since EC-RO selects low-rate codes to
satisfy $P_{\rm{out}}\leq\gamma$, its average rate increases. On the contrary,
outage probabilities of high-rate codes that are combined by MC and MC-RC
increase as $T$ increases. Thus, the average rate of MC and MC-RC decreases.

In Fig. 5(c), we show how the percentage of outages changes with $T$ for the
code designs in Fig. 5(b). Over $10^{8}$ time slots, at every $T$ time slots
we check if outage occurs101010Outage here refers to the case when the most
important source sequence cannot be decoded.. We then plot the percentage of
outage events. As shown in Fig. 5(c), all schemes have the same outage
percentage as $T$ increases since they use the same erasure code with
$P_{\rm{out}}\leq\gamma$ (MC and MC-RC use additional codes to improve the
rate). Up to $T=120$, all erasure codes have an outage probability larger than
$\gamma$. Thus, for these values of $T$, the code $(HT,1)$ is used whose
outage probability decreases as $T$ grows. As $T$ increases further, there are
erasure codes with $P_{\rm{out}}\leq\gamma$ and the outage percentage
decreases below $0.5\%$.

##  VI Conclusions

In this paper, we proposed to deploy multilevel codes both over space and time
to develop low-complexity proactive transmission mechanisms that offer
resilience against link blockages in mmWave networks. Our evaluations show
that our proposed schemes achieve attractive trade-offs between rate, delay,
and outage probability by providing a more graceful performance degradation
compared to the alternative scheme, while significantly reducing the
complexity.

## References

  * [1] 3GPP, “5g; typical traffic characteristics of media services on 3gpp networks (3gpp tr 26.925 version 17.1.0 release 17),” 3rd Generation Partnership Project (3GPP), Technical Report (TR), 2022. [Online]. Available: https://www.etsi.org/deliver/etsi_tr/126900_126999/126925/17.01.00_60/tr_126925v170100p.pdf
  * [2] J. Roche, R. Yeung, and K. P. Hau, “Symmetrical multilevel diversity coding,” _IEEE Trans. Inf. Theory_ , vol. 43, no. 3, pp. 1059–1064, 1997.
  * [3] R. Yeung and Z. Zhang, “On symmetrical multilevel diversity coding,” _IEEE Trans. Inf. Theory_ , vol. 45, no. 2, pp. 609–621, 1999.
  * [4] I. K. Jain, R. Kumar, and S. Panwar, “Driven by capacity or blockage? A millimeter wave blockage analysis,” in _2018 30th International Teletraffic Congress_ , vol. 01, 2018, pp. 153–159.
  * [5] M. Gapeyenko, A. Samuylov, M. Gerasimenko, D. Moltchanov, S. Singh, M. R. Akdeniz, E. Aryafar, N. Himayat, S. Andreev, and Y. Koucheryavy, “On the temporal effects of mobile blockers in urban millimeter-wave cellular scenarios,” _IEEE Transactions on Vehicular Technology_ , vol. 66, no. 11, pp. 10 124–10 138, 2017.
  * [6] Y. Wang, K. Venugopal, A. F. Molisch, and R. W. Heath, “Blockage and coverage analysis with mmWave cross street bss near urban intersections,” in _IEEE Int. Conf. Commun._ , 2017, pp. 1–6.
  * [7] V. Raghavan, L. Akhoondzadeh-Asl, V. Podshivalov, J. Hulten, M. A. Tassoudji, O. H. Koymen, A. Sampath, and J. Li, “Statistical blockage modeling and robustness of beamforming in millimeter-wave systems,” _IEEE Trans. Microw. Theory Tech._ , vol. 67, no. 7, pp. 3010–3024, 2019.
  * [8] C. Jeong, J. Park, and H. Yu, “Random access in millimeter-wave beamforming cellular networks: issues and approaches,” _IEEE Communications Magazine_ , vol. 53, no. 1, pp. 180–185, 2015.
  * [9] C. N. Barati, S. A. Hosseini, M. Mezzavilla, T. Korakis, S. S. Panwar, S. Rangan, and M. Zorzi, “Initial access in millimeter wave cellular systems,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 12, pp. 7926–7940, 2016.
  * [10] M. G. Dogan, Y. H. Ezzeldin, C. Fragouli, and A. W. Bohannon, “A reinforcement learning approach for scheduling in mmwave networks,” in _MILCOM 2021 - 2021 IEEE Military Communications Conference (MILCOM)_ , 2021, pp. 771–776.
  * [11] V. Va, X. Zhang, and R. W. Heath, “Beam switching for millimeter wave communication to support high speed trains,” in _2015 IEEE 82nd Vehicular Technology Conference (VTC2015-Fall)_ , 2015, pp. 1–5.
  * [12] M. G. Dogan, M. Cardone, and C. Fragouli, “Proactive resilience in 1-2-1 networks,” in _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 3220–3225.
  * [13] ——, “Multilevel code designs for mmwave networks,” in _GLOBECOM 2023 - 2023 IEEE Global Communications Conference_ , in press.
  * [14] ——, “Low-delay proactive mechanisms for resilient communication,” in _MILCOM 2023 - 2023 IEEE Military Communications Conference (MILCOM)_ , 2023, pp. 767–772.
  * [15] Y. H. Ezzeldin, M. Cardone, C. Fragouli, and G. Caire, “Gaussian 1-2-1 networks: Capacity results for mmWave communications,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 2, pp. 961–990, 2021.
  * [16] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” _J. Soc. Ind. Appl. Math._ , vol. 8, no. 2, pp. 300–304, 1960.
  * [17] W. C. Huffman and V. Pless, _Fundamentals of Error-Correcting Codes_ , 1st ed. Cambridge University Press, 2003.
  * [18] F. Rinaldi, A. Raschellà, and S. Pizzi, “5g nr system design: A concise survey of key features and capabilities,” _Wireless Networks_ , vol. 27, no. 8, p. 5173–5188, 2021.
  * [19] C. N. Barati, S. A. Hosseini, M. Mezzavilla, P. Amiri-Eliasi, S. Rangan, T. Korakis, S. S. Panwar, and M. Zorzi, “Directional initial access for millimeter wave cellular systems,” in _2015 49th Asilomar Conference on Signals, Systems and Computers_ , 2015, pp. 307–311.
  * [20] T. Nitsche, A. B. Flores, E. W. Knightly, and J. Widmer, “Steering with eyes closed: Mm-wave beam steering without in-band measurement,” in _IEEE Conference on Computer Communications_ , 2015, pp. 2416–2424.
  * [21] M. G. Dogan, M. Cardone, and C. Fragouli, “Proactive resilient transmission and scheduling mechanisms for mmwave networks,” _arXiv:2211.09307_ , 2022.

##  Appendix A Related Work

There exist several works in the literature that offer resilience against link
outages in mmWave networks by taking reactive approaches [8, 9, 19]. In [10],
to achieve resilience to link blockages, the authors explored a state-of-the-
art Soft Actor-Critic deep reinforcement learning algorithm, which adapts the
information flow through the mmWave network without using knowledge of the
link capacities or network topology. However, such reactive mechanisms add the
complexity of identification and adaptation, as well as feedback latency.
Several works have proposed proactive approaches for resilience by constantly
tracking users using side-channel information or external sensors [20, 11].
These solutions have limited accuracy, and possibly require sensitive
information, such as user location. In [12, 21], the authors leveraged
scheduling properties of the mmWave links as well as the blockage asymmetry to
achieve the average and the worst-case approximate capacities and proactively
offer resilience. They are different from our work where we propose coding
schemes to control what information is received, and to accommodate different
reliability requirements of different information streams. In [13], the
authors proposed low-complexity proactive transmission mechanisms for mmWave
networks by deploying symmetric multilevel codes over space (i.e., across
multiple paths). They proposed an optimization formulation to suitably balance
the rate with a graceful performance degradation. The authors then extended
this work to scenarios in which the path blockage probabilities are unequal
[14]. They defined the rate region to operate along with an optimization
formulation to select a high-performing set of rates for the source sequences.
These works are different from our work because: (i) the operation of their
proposed coding schemes relies on the existence of a multipath environment,
which might not always be practical; and (ii) these works focus on the rate-
outage probability trade-off without considering delay requirements. On the
contrary, in this paper: (i) we propose to deploy multilevel codes both over
space and time, which enables us to deploy the proposed coding schemes even if
the network does not support a multipath environment; (ii) our design
incorporates time correlation of blockages; and (iii) we consider the trade-
off between the rate, delay, and outage probability.

##  Appendix B Proof of Proposition 1

We consider blocks of $T$ time slots as shown in Fig. 6, and we derive the PMF
of the number of received packets over these time slots on path
$p_{j},j\in[1:H]$ (out of the $T$ transmitted packets). We note that, once a
blockage event starts on path $p_{j}$, $L$ consecutive time slots are blocked.
That means, while deriving the probabilities, we need to consider $L-1$ time
slots from the previous block as well, as illustrated in Fig. 6.

Figure 6: Illustration of time slots for $T=5,r=2$, and $i=1$.

Case 1: $0<r\leq T$. The event $\\{X_{j}=r\\}$ represents the case where
exactly $r$ packets (out of the $T$ transmitted packets) are received, i.e.,
$r$ out of the $T$ time slots are unblocked. Thus, the probability of the
event $\\{X_{j}=r\\}$ is equal to the sum of the probabilities of the events
in which exactly $r$ time slots are unblocked. In particular, each of these
events can be written as follows. In the first $r+i$ time slots (over the $T$
time slots that we consider) for $i\in[0:T-r]$, a new blockage event does not
begin. If $i<T-r$, a blockage event begins in the $(r+i+1)$th time slot and
the path $p_{j}$ stays blocked for the remaining $T-(r+i)$ time slots (i.e.,
the packets transmitted during these time slots are lost) since $L\geq T$. In
order to receive exactly $r$ packets we therefore need that: (i) a new
blockage event should not start over the last $L-1-i$ time slots in the
previous block; and (ii) a blockage event needs to begin in the last $(L-i)$th
time slot in the previous block for $i>0$. Thus, the probability of this event
is equal to,

$(1-\varepsilon_{j})^{r+i}\varepsilon_{j}^{\min\\{T-r-i,1\\}}(1-\varepsilon_{j})^{L-1-i}\varepsilon_{j}^{\min\\{i,1\\}}.$
(11)

Since the probability of the event $\\{X_{j}=r\\}$ is equal to the sum of the
probabilities of the aforementioned events for $i\in[0:T-r]$, we obtain the
probability presented in Proposition 1.

Case 2: $r=0$. The probability of the event $\\{X_{j}=0\\}$ is equal to the
sum of the probabilities of the events in which all the $T$ time slots are
blocked. In particular, these events can be due to one of the following
events:

  * •

A new blockage event starts in the first time slot with probability
$\varepsilon_{j}$. Then since $L\geq T$, all $T$ time slots will be blocked
independently of what happens in the previous or following time slots.

  * •

A new blockage event does not start in the first $i$ time slots for
$i\in[1:T]$. Then, a new blockage event starts in the $(i+1)$th time slot if
$i<T$. In this case, there should be at least one blockage event that started
in one of the $L-i$ time slots of the previous block. This ensures that all
$T$ time slots are blocked. Thus, the probability of this event is equal to,

$(1-\varepsilon_{j})^{i}\varepsilon_{j}^{\min\\{T-i,1\\}}\left(1-(1-\varepsilon_{j})^{L-i}\right).$
(12)

Since the probability of event $\\{X_{j}=0\\}$ is equal to the summation of
the probabilities of these events for $i\in[1:T]$, we obtain the probability
presented in Proposition 1. This concludes the proof of Proposition 1.

(a) $H=3$

(b) $H=3,L=400$.

(c) $H=1,L=400$.

Figure 7: Channel illustration for $T=100$, and $A=50,000$.

##  Appendix C Proof of Proposition 2

We start with the probabilities derived in Proposition 1. We have that

$\displaystyle P_{X_{j}}(0)$
$\displaystyle=\varepsilon_{j}+\sum_{i=1}^{T-1}(1-\varepsilon_{j})^{i}\varepsilon_{j}\left(1-(1-\varepsilon_{j})^{L-i}\right)$
$\displaystyle\quad+(1-\varepsilon_{j})^{T}\left(1-(1-\varepsilon_{j})^{L-T}\right)$
$\displaystyle=\varepsilon_{j}+\varepsilon_{j}\left(\sum_{i=1}^{T-1}\left((1-\varepsilon_{j})^{i}-(1-\varepsilon_{j})^{L}\right)\right)$
$\displaystyle\quad+(1-\varepsilon_{j})^{T}-(1-\varepsilon_{j})^{L}$
$\displaystyle=\varepsilon_{j}+\varepsilon_{j}\left(\frac{(1-\varepsilon_{j})-(1-\varepsilon_{j})^{T}}{\varepsilon_{j}}-(T-1)(1-\varepsilon_{j})^{L}\right)$
$\displaystyle\quad+(1-\varepsilon_{j})^{T}-(1-\varepsilon_{j})^{L}$
$\displaystyle=1-\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}-(1-\varepsilon_{j})^{L}.$

We note that from the above, we readily obtain that

$\displaystyle\lim_{L\to\infty}P_{X_{j}}(0)=1,$

which follows since $\lim_{L\to\infty}(1-\varepsilon_{j})^{L}=0$.

Similarly, from Proposition 1 we have that,

$P_{X_{j}}(T)=(1-\varepsilon_{j})^{T}(1-\varepsilon_{j})^{L-1}.$

Then, we can write $P(X_{j}=0)+P(X_{j}=T)$ as follows,

$\displaystyle P_{X_{j}}(0)+P_{X_{j}}(T)$
$\displaystyle=1-\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}-(1-\varepsilon_{j})^{L}$
$\displaystyle\quad+(1-\varepsilon_{j})^{T}(1-\varepsilon_{j})^{L-1}$
$\displaystyle=1-\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}$
$\displaystyle\quad-(1-\varepsilon_{j})^{L}\left(1-(1-\varepsilon_{j})^{T-1}\right).$
(13)

Now, the approximation in Proposition 2 holds if one of the following two
conditions holds: (i) $\varepsilon_{j}(T-1)\ll 1$, or (ii)
$(1-\varepsilon_{j})^{L}\ll 1$ and
$\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}\ll 1$.

Case 1. When $\varepsilon_{j}(T-1)\ll 1$, we can use the Binomial
approximation as follows,

$\displaystyle(1-\varepsilon_{j})^{T-1}\approx 1-(T-1)\varepsilon_{j}.$

By using the above approximation inside (13), we obtain

$\displaystyle P_{X_{j}}(0)+P_{X_{j}}(T)\approx
1-2\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}.$

If the condition $\varepsilon_{j}(T-1)\ll 1$ in Proposition 2 is satisfied,
then $\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}\ll 1$ and hence,

$P_{X_{j}}(0)+P_{X_{j}}(T)\approx 1.$

Case 2. When $(1-\varepsilon_{j})^{L}\ll 1$ and
$\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}\ll 1$, the second term in (13) is
$\varepsilon_{j}(T-1)(1-\varepsilon_{j})^{L}\ll 1$. Similarly, since
$(1-\varepsilon_{j})^{L}\ll 1$, also the last term in (13) is
$(1-\varepsilon_{j})^{L}\left(1-(1-\varepsilon_{j})^{T-1}\right)\ll 1$. Hence,

$P_{X_{j}}(0)+P_{X_{j}}(T)\approx 1.$

This concludes the proof of Proposition 2.

##  Appendix D Numerical Analysis of Channel

We here perform numerical evaluations for the channel analysis presented in
Section III. The specific network configuration under consideration is a 1-2-1
topology, characterized by a code duration of $T=100$ time slots. We assume
that TTI duration $t_{d}=250~{}\mu$s [18]. The arrival of blockers on every
path follows a PPP with an intensity of $3$ blockers per second111111That is,
$\alpha_{j}=7.5\times 10^{-4}$ blockers per TTI for $j\in[1\\!:\\!H]$ in (3)..
We observe that for this Poisson intensity, we have $\varepsilon_{j}=7.5\times
10^{-4}$. This satisfies the condition $\varepsilon_{j}(T-1)\ll 1$ in
Proposition 2.

First, we consider the network in Fig. 2 with $H=3$ edge-disjoint paths. Over
this network, we observe the effect of a multipath environment under the
considered blockage model. In Fig. 7(b), we present the histogram representing
the distribution of the number of received packets for the blockage duration
$L=400$ time slots. In order to plot this histogram, we simulate blockage
realizations for the network in Fig. 2 and over $A=50,000$ time slots in
total. We find the number of received packets at every $T$ time slots, and we
plot their distribution in Fig. 7(b). We note that the total number of
transmitted packets at every $T$ time slots is $HT=300$.

As discussed in Section III, when one of the conditions in Proposition 2 is
satisfied and there are $H$ paths, the number of received packets is likely to
take values $jT$ for $j\in[0:H]$. This concentration is observable in Fig.
7(b), where a considerable proportion of mass is evident at intervals of $T$,
such as $0,T,2T,3T$. Consequently, this concentration contributes to an
increased variance in the channel behavior, which motivates the use of
multilevel coding in a multipath scenario. In Fig. 7(a), we show how the
standard deviation of the number of received packets from the mean changes as
the blockage duration (in time slots) $L$ increases. As $L$ increases, we
observe this concentration around specific values $jT$ for $j\in[0:H]$, as
mentioned above. And due to that, standard deviation also increases.

To numerically verify Proposition 2, we also consider the case for $H=1$. In
Fig. 7(c), we observe consistent results with our analysis in Proposition 2.
Specifically, the distribution is primarily concentrated around $0$ and $T$,
allowing us to numerically confirm that $P_{X_{1}}(0)+P_{X_{1}}(T)\approx 1$.


# Certifying the Restricted Isometry Property is Hard

Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin A.S.
Bandeira is with the Program in Applied and Computational Mathematics,
Princeton University, Princeton, New Jersey 08544 USA (e-mail:
ajsb@math.princeton.edu).E. Dobriban is with the Department of Statistics,
Stanford University, Stanford, California 94305 USA (e-mail:
dobriban@stanford.edu).D.G. Mixon is with the Department of Mathematics and
Statistics, Air Force Institute of Technology, Wright-Patterson AFB, Ohio
45433 USA (e-mail: dustin.mixon@afit.edu).W.F. Sawin is with the Department of
Mathematics, Princeton University, Princeton, New Jersey 08544 USA (e-mail:
wsawin@math.princeton.edu).The authors thank Boris Alexeev for reading this
manuscript and providing thoughtful comments and suggestions. Bandeira was
supported by NSF Grant No. DMS-0914892, and Mixon was supported by the A.B.
Krongard Fellowship. The views expressed in this article are those of the
authors and do not reflect the official policy or position of the United
States Air Force, Department of Defense, or the U.S. Government.

###### Abstract

This paper is concerned with an important matrix condition in compressed
sensing known as the restricted isometry property (RIP). We demonstrate that
testing whether a matrix satisfies RIP is ${\mathsf{NP}}$-hard. As a
consequence of our result, it is impossible to efficiently test for RIP
provided ${\mathsf{P}}\neq{\mathsf{NP}}$.

##  I Introduction

It is now well known that compressed sensing offers a method of taking few
sensing measurements of high-dimensional sparse vectors, while at the same
time enabling efficient and stable reconstruction [1]. In this field, the
restricted isometry property is arguably the most popular condition to impose
on the sensing matrix in order to acquire state-of-the-art reconstruction
guarantees:

######  Definition 1.

We say a matrix $\Phi$ satisfies the $(K,\delta)$-restricted isometry property
(RIP) if

$(1-\delta)\|x\|^{2}\leq\|\Phi x\|^{2}\leq(1+\delta)\|x\|^{2}$

for every vector $x$ with at most $K$ nonzero entries.

To date, RIP-based reconstruction guarantees exist for Basis Pursuit [2],
CoSaMP [3] and Iterative Hard Thresholding [4], and the ubiquitous utility of
RIP has made the construction of RIP matrices a subject of active research
[5]–[7]. Here, random matrices have found much more success than deterministic
constructions [5], but this success is with high probability, meaning there is
some (small) chance of failure in the construction. Furthermore, RIP is a
statement about the conditioning of all $\binom{N}{K}$ submatrices of an
$M\times N$ sensing matrix, and so it seems computationally intractable to
check whether a given instance of a random matrix fails to satisfy RIP; it is
widely conjectured that certifying RIP for an arbitrary matrix is
${\mathsf{NP}}$-hard. In the present paper, we prove this conjecture.

######  Problem 2.

Given a matrix $\Phi$, a positive integer $K$, and some $\delta\in(0,1)$, does
$\Phi$ satisfy the $(K,\delta)$-restricted isometry property?

In short, we show that any efficient method of solving Problem 2 can be called
in an algorithm that efficiently solves the ${\mathsf{NP}}$-complete subset
sum problem. As a consequence of our result, there is no method by which one
can efficiently test for RIP provided ${\mathsf{P}}\neq{\mathsf{NP}}$. This
contrasts with previous work [8], in which the reported hardness results are
based on less-established assumptions on the complexity of dense subgraph
problems.

In the next section, we review the basic concepts we will use from
computational complexity, and Section 3 contains our main result.

##  II A brief review of computational complexity

In complexity theory, problems are categorized into complexity classes
according to the amount of resources required to solve them. For example, the
complexity class ${\mathsf{P}}$ contains all problems which can be solved in
polynomial time, while problems in ${\mathsf{EXP}}$ may require as much as
exponential time. Problems in ${\mathsf{NP}}$ have the defining quality that
solutions can be verified in polynomial time given a certificate for the
answer. As an example, the graph isomorphism problem is in ${\mathsf{NP}}$
because, given an isomorphism between graphs (a certificate), one can verify
that the isomorphism is legitimate in polynomial time. Clearly,
${\mathsf{P}}\subseteq{\mathsf{NP}}$, since we can ignore the certificate and
still solve the problem in polynomial time.

While problem categories provide one way to describe complexity, another
important tool is the polynomial-time reduction, which allows one to show that
a given problem is “more complex” than another. To be precise, a polynomial-
time reduction from problem $A$ to problem $B$ is a polynomial-time algorithm
that solves problem $A$ by exploiting an oracle which solves problem $B$; the
reduction indicates that solving problem $A$ is no harder than solving problem
$B$ (up to polynomial factors in time), and we say “$A$ reduces to $B$,” or
$A\leq B$. Such reductions lead to some of the most popular definitions in
complexity theory: We say a problem $B$ is called ${\mathsf{NP}}$-hard if
every problem $A$ in ${\mathsf{NP}}$ reduces to $B$, and a problem is called
${\mathsf{NP}}$-complete if it is both ${\mathsf{NP}}$-hard and in
${\mathsf{NP}}$. In plain speak, ${\mathsf{NP}}$-hard problems are harder than
every problem in ${\mathsf{NP}}$, while ${\mathsf{NP}}$-complete problems are
the hardest of problems in ${\mathsf{NP}}$.

Contrary to popular intuition, ${\mathsf{NP}}$-hard problems are not merely
problems that seem to require a lot of computation to solve. Of course,
${\mathsf{NP}}$-hard problems have this quality, as an ${\mathsf{NP}}$-hard
problem can be solved in polynomial time only if ${\mathsf{P}}={\mathsf{NP}}$;
this is an open problem, but it is widely believed that
${\mathsf{P}}\neq{\mathsf{NP}}$ [9]. However, there are other problems which
seem hard but are not known to be ${\mathsf{NP}}$-hard (e.g., the graph
isomorphism problem). As such, while testing for RIP in the general case seems
to be computationally intensive, it is not obvious whether the problem is
actually ${\mathsf{NP}}$-hard. Indeed, by the definition of
${\mathsf{NP}}$-hard, one must compare its complexity to the complexity of
every problem in ${\mathsf{NP}}$. To this end, notice that $A\leq B$ and
$B\leq C$ together imply $A\leq C$, and so to demonstrate that a problem $C$
is ${\mathsf{NP}}$-hard, it suffices to show that $B\leq C$ for some
${\mathsf{NP}}$-hard problem $B$.

In the present paper, we demonstrate the hardness of certifying RIP by
reducing from the following problem:

######  Problem 3.

Given a matrix $\Psi$ and some positive integer $K$, do there exist $K$
columns of $\Psi$ which are linearly dependent?

Problem 3 has a brief history in computational complexity. First, McCormick
[10] demonstrated that the analogous problem of testing the girth of a
transversal matroid is ${\mathsf{NP}}$-complete, and so by invoking the
randomized matroid representation of Marx [11], Problem 3 is hard for
${\mathsf{NP}}$ under randomized reductions [12]. Next, Khachiyan [13] showed
that the problem is ${\mathsf{NP}}$-hard by focusing on the case where $K$
equals the number of rows of $\Psi$; using a particular matrix construction
with Vandermonde components, he reduced this instance of the problem to the
subset sum problem. Recently, Tillmann and Pfetsch [14] used ideas similar to
McCormick’s to strengthen Khachiyan’s result: they prove Problem 3 is
${\mathsf{NP}}$-hard without focusing on such a specific instance of the
problem. Each of these complexity results use $M\times N$ matrices with
integer entries whose binary representations take $\leq p(M,N)$ bits for some
polynomial $p$; we will exploit this feature in our proof.

##  III Main result

######  Theorem 4.

Problem 2 is ${\mathsf{NP}}$-hard.

###### Proof.

Reducing from Problem 3, suppose we are given a matrix $\Psi$ with integer
entries. Letting $\mathrm{Spark}(\Psi)$ denote the size of the smallest
collection of linearly dependent columns of $\Psi$, we wish to determine
whether $\mathrm{Spark}(\Psi)\leq K$. To this end, we take $P\leq 2^{p(M,N)}$
to be the size of the largest entry in $\Psi$, and define
$C=2^{\lceil\log_{2}\sqrt{MN}P\rceil}$ and $\Phi=\frac{1}{C}\Psi$; note that
we choose $C$ to be of this form instead of $\sqrt{MN}P$ to ensure that the
entries of $\Phi$ can be expressed in ${\mathsf{poly}}(M,N)$ bits without
truncation. Of course, linear dependence between columns is not affected by
scaling, and so testing $\Phi$ is equivalent to testing $\Psi$. In fact, since
we plan to appeal to an RIP oracle, it is better to test $\Phi$ since the
right-hand inequality of Definition 1 is already satisfied for every
$\delta>0$:

$\displaystyle\|\Phi\|_{2}\leq\sqrt{MN}\|\Phi\|_{\mathrm{max}}=\sqrt{MN}\frac{P}{C}\leq
1\leq\sqrt{1+\delta}.$

We are now ready to state the remainder of our reduction: For some value of
$\delta$ (which we will determine later), ask the oracle if $\Phi$ is
$(K,\delta)$-RIP; then

$\begin{array}[]{rcll}\mbox{(i)}&\mbox{$\Phi$ is
$(K,\delta)$-RIP}&\Longrightarrow&\mathrm{Spark}(\Psi)>K,\\\
\mbox{(ii)}&\mbox{$\Phi$ is not
$(K,\delta)$-RIP}&\Longrightarrow&\mathrm{Spark}(\Psi)\leq K.\end{array}$

The remainder of this proof will demonstrate (i) and (ii).

Note that (i) immediately holds for all choices of $\delta\in(0,1)$ by the
contrapositive. Indeed, $\mathrm{Spark}(\Psi)\leq K$ implies the existence of
a nonzero vector $x$ in the nullspace of $\Phi$ with $\leq K$ nonzero entries,
and $\|\Phi x\|^{2}=0<(1-\delta)\|x\|^{2}$ violates the left-hand inequality
of Definition 1. For (ii), we also consider the contrapositive. When
$\mathrm{Spark}(\Psi)>K$, we have that every size-$K$ subcollection of
$\Psi$’s columns is linearly independent. Letting $\Psi_{\mathcal{K}}$ denote
the submatrix of columns indexed by a size-$K$ subset
$\mathcal{K}\subseteq\\{1,\ldots,N\\}$, this implies that
$\lambda_{\mathrm{min}}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})>0$, and so
$\det(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})>0$. Since the entries of
$\Psi$ lie in $\\{-P,\ldots,P\\}$, we know the entries of
$\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}}$ lie in
$\\{-MP^{2},\ldots,MP^{2}\\}$, and since
$\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}}$ is integral with positive
determinant, we must have $\det(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})\geq
1$. In fact,

$\displaystyle 1$
$\displaystyle\leq\det(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})$
$\displaystyle=\prod_{k=1}^{K}\lambda_{k}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})$
$\displaystyle\leq\lambda_{\mathrm{min}}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})\cdot\lambda_{\mathrm{max}}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})^{K-1}$
$\displaystyle\leq\lambda_{\mathrm{min}}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})\cdot\big{(}K\|\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}}\|_{\mathrm{max}}\big{)}^{K-1},$

and so we can rearrange to get

$\displaystyle\lambda_{\mathrm{min}}(\Phi_{\mathcal{K}}^{*}\Phi_{\mathcal{K}})$
$\displaystyle=\frac{1}{C^{2}}\lambda_{\mathrm{min}}(\Psi_{\mathcal{K}}^{*}\Psi_{\mathcal{K}})$
$\displaystyle\geq\frac{1}{C^{2}(KMP^{2})^{K-1}}\geq 2^{-5MNp(M,N)},$

where the last inequality follows from $K\leq M\leq N$ and other coarse
bounds. Therefore, if we pick $\delta:=1-2^{-5MNp(M,N)}$, then since our
choice for $\mathcal{K}$ was arbitrary, we conclude that $\Phi$ is
$(K,\delta)$-RIP whenever $\mathrm{Spark}(\Psi)>K$, as desired. Moreover,
since $\delta$ can be expressed in the standard representation using
${\mathsf{poly}}(M,N)$ bits, we can ask the oracle our question in polynomial
time. ∎

It is important to note that Theorem 4 is a statement about testing for RIP in
the worst case; this result does not rule out the existence of matrices for
which RIP is easily verified (e.g., using coherence in conjunction with the
Gershgorin circle theorem for small values of $K$ [5]).

## References

  * [1] E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005) 4203–4215.
  * [2] E.J. Candès, The restricted isometry property and its implications for compressed sensing, C. R. Acad. Sci. Paris, Ser. I 346 (2008) 589–592.
  * [3] D. Needell, J.A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (2009) 301–321.
  * [4] T. Blumensath, M.E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009) 265–274.
  * [5] A.S. Bandeira, M. Fickus, D.G. Mixon, P. Wong, The road to deterministic matrices with the restricted isometry property, Available online: arXiv:1202.1234
  * [6] R. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007) 918–925.
  * [7] T. Tao, Open question: Deterministic UUP matrices, Available online: http://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-matrices
  * [8] P. Koiran, A. Zouzias, On the certification of the restricted isometry property, Available online: arXiv:1103.4984
  * [9] S. Cook, The P versus NP problem, Available online: http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
  * [10] S.T. McCormick, A Combinatorial Approach to Some Sparse Matrix Problems. Ph.D. Thesis, Stanford University (1983)
  * [11] D. Marx, A parameterized view on matroid optimization problems, Theor. Comput. Sci. 410 (2009) 4471–4479.
  * [12] B. Alexeev, J. Cahill, D.G. Mixon, Full spark frames, Available online: arXiv:1110.3548
  * [13] L. Khachiyan, On the complexity of approximating extremal determinants in matrices, J. Complexity 11 (1995) 128–153.
  * [14] A.M. Tillmann, M.E. Pfetsch, The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing, Available online: arXiv:1205.2081