y1 xj zj

si s si i

Target

xi xi sj s sj

xj x j xi xi sj sj si si

(a) (c) (c) (a) (b) (b) (a) (b) (c) Fig. 1. Example 1: graphical models. (a) Quadtree (b) Ising model. (c) model. (c) (c) Ising form a connected tree on th Figure 1:Figure 1: graphical models. (a) models. (a) Quadtree model. Ising Isingmodel. (top-left) model withCS Example The graphical Quadtree of the piecewise-smooth model Ising measurements. Figure Examplesparse coecientsmodel. model. (b) (b) Ising signal with CS model with CS measurements. the sparse coecients of the background subtracted image from a surveillance camera (bo measurements. whereas basis,

Graphical model

State-of-the-art CS

Graphical model-based

3 Proposed Research: Theory and Model-based 3 Proposed Research: Theory andsignal Methods forimprove the performance of the state-of-the-art CS knowledge on the structure of sparse Methods for Model-based coecients to Compressive Sensing or continuous valued).number of compressive measurements. for the same An undirected edge e E indicates dependence between the corresponding pair of Compressive Sensing
randomWhile CS has the potential to revolutionizeof z acquisition,. encoding, and.processing in a number variables; that is, the conditional density data given z ,. , z , z ,. is a function of only
cluster spatially on a Markov random eld. The graphical model-based CS theory I am developing exploits
v 1 v1 v+1 While CS has the potential towork remains beforeacquisition, encoding, and processing in a number of applications, much revolutionize data it is ready for real-world deployment. In particular, for I much work. A directed edge indicates that and practice leverage concepts from for ofthe neighborsam workingitsremains before it is ready theory the including MarkovIn particular,state- hidden Mark applications,connected towith a range of graphical for real-world deployment. of zv is a elds and CS to truly live up vname, it is crucial that the models, conditional density random function CS to truly livevariables withcompression algorithms. v.diversepractice leverage concepts from state-of sensor netwo which have broad it is crucial that manyIn Denote disciplines, such as the key ingredient virtually all such algorithms, computer vision, of only of-the-art transform edges directed in the theory and the random variables for any subset S those up its name, applications towards of-the-art transform compressionjustIn collaboration withall such algorithms, the key ingredient algorithms. In virtually but also the coefcient structure. Via the is a signal model for not communication systems. the coefcient sparsity Richard G. Baraniuk, I have introduced preliminar isthe signal model z S not vjust the. coefcient sparsity but also groundworkvertices, where there exists a vertices V as four tasks, thisS} A clique layis a fully connected subset of required for practical CS following for {z |v project will C the mathematical the coefcient structure. Via the and recovery algorithms with provableperformance to incorporate structural prior information on spa followingefour tasks, this projectpairand vertices in guaranteeslimits of thisrequired forof techniques. an edgein Navy-relevant applications of study mathematical groundwork new family practical CS C connecting every will lay the the the subgraph. coecients in CS recovery. Structural priors reduce this new family of techniques. in Navy-relevant applications and study the performance limits ofthe degrees of freedom of a sparse signal by pe A directedTask 1: Model-based CS a directed graph without directed loops (so that for any v , there acyclic 3.1 certain graph (DAG) is congurations of its sparse coecients. My preliminary work creates a only deterministic recovery 3.1 no directedMotivationbegin and endtools for If we denote progress to integrate graphical models with CS (se are Task 1: Model-based CS recovery 3.1.1 paths that for recovery algorithms and with v ). theoretical the set of parents of node v as (v), then it is Motivationthat the from a DAG towardsapproach is to vision. 3.1.1 easy to rst departure pdf of the step can be factorized as my adopt a more general, probabilistic Our show is an important standard CS realizing hence, it (Bayesian)also developing a multimodal CS signal acquisition or compressibility in each the common g I am viewpoint. A probabilistic sparsity model enforces sparsity Our rstcoefcient by heavily weighting zero approach is to adopt a more framework to leverage departure from the standard CS or small-magnitude values in the general, probabilistic probability distribution, p(z) = p(z |z (v) ). (2) (Bayesian) viewpoint. A largemultimodal datamodel vprobabilities to obtainextraction. The ofeach model structureprobabilistic sparsity vV low enforces sparsity or compressibility inintrinsic information in range of values with eective information a small number large for while allowing a coefcient by heavily weighting zero or small-magnitudemodelsalone. This used to explain known coefcients. As we be captured with aprobabilistic valuescan the probability distribution, problems cannot saw in Section 2.2, single modality in also be observation is a highlight of my w An example isaCS techniquesof valuesthis Pursuitprobabilities to obtain a small number ofof radar while allowing shown range such as Basis can be Denoising. standard large in Figure 1(a); with low used to model a quadtree decomposition large James H. McClellan and Rama Chellappa where I used particle lters and variational analysis coefcients.Theapower of probabilistic2.2, probabilistic can easily move beyond independent coefcient As we saw in Section models is that we models can also images [9] or multiscale wavelet decomposition of natural images [12]. be used to explain known approximations of the conceptcomputations via calculus of variationsto fuse acoustic and video obs standard models to generalize high costPursuit Denoising. CS techniques such as Basis of sparsity to structured sparsity. Such models are already emIn contrast, Figure 1(b) depicts an undirected graph with loops in a broad set of applications. For instance, to (see Fig. 2). My multimodal coding can easily moveto represent the Ising model, where ployed in state-of-the-art transformthat we and statistical signal processing algorithms based on The power of probabilistic models isframework is relevant beyond independent coefcient wavelets, where natural images induce wavelet between the that Such along of EEG and the the variables s z theneuroimaging correlates the high temporal resolution are z. Similarly, models to generalize represent the of sparsity to structured sparsity. clustermodelsthe branches of the high spatial r brain activity, concept latent connections coefcients signal coefcients x already emwavelet tree [10, 11, 3335]. codingexplore a range of statistical models that have proved indiswill and statistical signal processing ployed in state-of-the-art transformWe the Ising model to the non-traditional algorithms based on Figure 1(c) illustrates an extensionsuch applications, new CS measurement signal processing will setting, which we techniques beyon of fMRIfor modeling the of modalities. pensable natural images Incoefcient and support structure of sparsifying transforms. Our focus wavelets, where induce wavelet coefcients that cluster along the branches of the correlations powerful class graphical acquire signals and that will be on the are needed toof appropriate, non-negative compatibility function their reprerevisit tree [10, III-B. By dening aneciently models [30, 31, 3638] to understand C (z C ) origin. wavelet in Section11, 3335]. We will explore a range of statistical modelsprovide geometricalfor each that have proved indissentations for probability distributions (recall Section 2.3). pensable forTo the Hammersley-Clifford theorem [7]structurethe sparsifying investigating inference methods that modeling the coefcient and acquisition framework, I am transforms. Our as clique C G, support my multimodal support enables of pdf of the graph to be written focus rectly on the explicit signal reconstruction, such as graphical model s will be on the powerfulcompressive samples without 31, 3638] that provide geometrical repre3.1.2 Relevant class of graphical models [30, graphical models 1 sentations for probability distributions (recall= detection. C ), 2.3). parameter estimation, and anomaly (3) p(z) SectionC (z Multimodal signals typically have dierent informati In preliminary work, we have identied a Z range of both directed and undirected graphical models C while a single snapshot captured by a camera is meaningful in spatial context, acoustic data must b that are promising for new CS 3.1.2 Relevant graphical models recovery and inference techniques. gated to understand the temporally spread is information. Multimodal data fusion where Z is the partition function that ensures that p(z)out properly normalized. The product in (3) isthen requires m In preliminary work,spatio-temporal data volumes, whose dimensionality can be reduced via CS. In turn, di large-scale we have identied a range of both directed and undirected graphical models taken over all cliques C in the graph G. that are promising for new compressive and inference techniques. cessing with the CS recovery samples improves the eciency of information extraction. My approac 7 2) Inference mechanisms: We refer to the process of estimating local marginal distributions or other roots in iterative approximation algorithms where small-scale optimization problems are solved in summary statisticsdesired performance is obtained. I will also exploit ideas from and contribute solutions to s until the of z , such as the most probable conguration of f (x|y), as Bayesian inference. 7 algorithms that work on random measurements.

While checking whether a measurement matrix satises the K -RIP, RSC, etc. has running time exponential in K and N , random matrices with iid subgaussian entries work with high probability provided M = O(K log(N/K)). Random matrices also have a so-called universality property in that, for any choice of orthonormal basis matrix , also has the K -RIP with high probability. This is useful when the signal is sparse in some basis other than the canonical basis. 3) Tractable recovery algorithms: To recover the signal x from y in (1), we exploit our a priori knowledge of its sparsity or compressibility. For example, to recover strictly sparse signals when there is no measurement noise, we can seek the sparsest x that agrees with the measurements y. While this optimization can recover a K -sparse signal from just M = 2K compressive measurements, it is not only a combinatorial, NP-hard problem, but also is not stable in the presence of noise [1]. Tractable recovery algorithms rely on conditions such as the RIP and RSC for stability and correctness and therefore require at least M = O(K log(N/K)) measurements. They can be grouped into two main camps: convex optimization and greedy approximation. The rst camp relies on a convex relaxation of seeking sparse solutions:

x = arg min x x

minimization as

s.t. y = x.

This optimization problem is known as basis pursuit and corresponds to a linear program that can be solved in polynomial time [1, 4, 5]. Adaptations to deal with additive noise in (1) have also been proposed; examples include basis pursuit with denoising (BPDN), and the least absolute shrinkage and selection operator (LASSO). The second camp nds the sparsest x agreeing with the measurements y through an iterative, greedy search over the coefcients. Example algorithms include iterative hard thresholding (IHT), compressive sampling matching pursuit (CoSaMP), and Subspace Pursuit (SP) [1]. Currently, convex optimization obtains the best recovery performance in theory, while its greedy counterparts, such as IHT, CoSaMP, and SP, offer desirable computational trade-offs, e.g., O N log2 N vs. O M 2 N 1.5 (interior point methods) [1]. Interestingly, algorithms in both camps have similar theoretical recovery guarantees from M = O(K log(N/K)) when the measurement matrix satises K -RIP with an algorithm dependent 2K (e.g., 2K < for basis pursuit [5]):

C1 K 1/2 x xK

+ C2 n 2 ,

which we refer to as an

guarantee, where the subscripts are matched to the norms adjacent to the is known as the irrecoverable energy.

inequality. In (7), x is the algorithm output, C1 and C2 are algorithm-dependent constants, and xK is the signal-dependent best K -sparse approximation. The term xxK 7
When the signals are compressible, we can never recover them fully under dimensionality reduction; we can only approximately recover them and only when r 1 in (4). III. G RAPHICAL MODELS FOR STRUCTURED SPARSITY While CS has the potential to revolutionize data acquisition, encoding, and processing in a number of applications, much work remains before it is ready for real-world deployment. In particular, for CS to truly live up its name, it is crucial that the theory and practice leverage concepts from state-of-the-art transform compression algorithms. In virtually all such algorithms, the key ingredient is a signal model for not just the coefcient sparsity but also the coefcient structure. As we saw in Section II, graphical models provide natural framework for capturing such dependencies among sparse signal coefcients. Hence, we review below some of the graphical models that are relevant for structured sparsity and the algorithms that result for sparse signal recovery. A. Sparsity priors Our rst departure from the standard, deterministic CS approach is to adopt a more general, Bayesian viewpoint as several others have pursued [1, 17, 18]. A probabilistic sparsity prior enforces sparsity or compressibility in each coefcient by heavily weighting zero or small-magnitude values in the probability distribution, while allowing a large range of values with low probabilities to obtain a small number of large coefcients. While this is expected in principle, we also require a generative aspect for such priors in order to build up structured sparsity models; that is, their statistical realizations result in sparse or compressible signals. This, in turn, is crucial for statistical consistency in high-dimensional scalings of the sparse signal recovery problem. Two-state mixture models are the canonical iid models for generating strictly sparse signals. Among mixture models, the spike-and-slab prior stipulates a density with a spike at zero surrounded symmetrically by a uniform distribution with specied boundaries. The mixture probability of the spike at zero approximately determines the percentage of zero coefcients of the signal, and the uniform distribution establishes the distribution of the signal coefcients on the signal support. To model compressible signals, we can use compressible priors, whose statistical realizations exhibit the power-law decay in (4) [15]. For algorithmic recovery guarantees for CS, we must have r 1 for such priors (c.f. (4)). For instance, Table III-A demonstrates that N -sample iid realizations of generalized Pareto, Students t, Frechet, and log-logistics distributions (each parameterized by a shape parameter

q > 0 and a scale parameter > 0) are compressible with parameter r = q. There also exist non-iid
compressible priors; multivariate Lomax distribution provides an elementary example whose pdf is given 8
TABLE I E XAMPLE DISTRIBUTIONS AND THE COMPRESSIBILITY PARAMETERS OF THEIR IID REALIZATIONS
Distribution Generalized Pareto Students t Fr chet e Log-Logistic Laplacian

pdf 1+

|x| (q+1) (q+1)/2 (x/)q

R N 1/q

2((q+1)/2) q(q/2) 1/q

r q N 1/q q q q log N

((q+1)/2) 2(q/2)

(q/) (x/)

1/q 1/q
(q/)(x/)q1 [1+(x/)q ]|x|/ e 2

log N

by MLD(x; q, ) 1 +

1 |xi |

[15]. The compressibility parameter MLD is simply r = 1,
irrespective of its shape parameter. To illustrate how we can exploit probabilistic priors in sparse signal recovery, we focus on two compressible priors on x: MLD and Students t. While MLD is relatively unknown, the Students t distribution has enjoyed tremendous attention in many fundamental problems, such as statistical modeling of natural images, relevance vector machines (RVM) and automatic relevance determination, and dictionary learning. We consider the case when there is no noise; the observations are then given by y = x with
M = O(K log(N/K)), which has innitely many solutions for x, as discussed in Section II. We know
that such projections preserve the information of the largest K -coefcients of signal realizations. We will assume that the parameters of MLD and the Students t priors are matched (i.e., the shape parameter of Students t is 1) so that the statistical realizations of both priors have the same decay prole. 1) MLD and basis pursuit: We rst exploit the MLD likelihood function for sparse signal recovery. For instance, when we ask for the solution that maximizes the MLD likelihood given y for i = , it is easy to see that we obtain the basis pursuit algorithm formulation in (6). In contrast, the conventional probabilistic motivation for the basis pursuit algorithm assumes that x is iid Laplacian, e.g., f (x) exp ( x 1 /) for some R+. We then face the optimization problem (6), when we seek the most likely signal from the Laplacian prior given y. Unfortunately, iid Laplacian realizations cannot be approximated as sparse since their compressibility parameter is r = log N , which is greater than 1 in general (c.f. Table III-A); it can be shown that x xK 1 x 1 requires K (1 )N with high probability [15]. Hence, while the

minimization correctly recovers the sparse vectors from M = O(K log(N/K)), it seems
that it does not correspond to an iid Laplacian prior on the sparse signal coefcients in a consistent Bayesian framework and may correspond to the MLD prior as this example demonstrates. 2) Students t and iterative reweighted least squares: We now exploit the Students t likelihood function 9
for sparse signal recovery, similar to MLD likelihood function above:
x = max f (x) = min x x log 1 + 2 xi2 , s.t. y = x.
Unfortunately, (8) is a non-convex problem. However, we can circumvent the non-convexity in (8) using a simple variational Bayes idea where we iteratively obtain a tractable upperbound on the log-term in (8) using the following inequality: u, v (0, ), log u log v + u/v 1. After some straightforward calculus, we obtain the iterative algorithm below, indexed by k , where x{k} is the k -th iteration estimate (x{0} = 0):

x{k} = min x

2 wi,{k} xi2 , s.t. y = x ; where wi,{k} = 2 + xi,{k} i 1
The decoding scheme in (9) is well-known as the iterative reweighted least squares (IRLS), where each iteration has an analytical solution [19]. Both priors in the above algorithms are trying to approximate their signal realizations, which have the same decay prole, and yet result in radically different algorithms. Both schemes have provable recovery guarantees; however, they differ in terms of their computational costs: O(M 2 N ) (IRLS) vs. O(M 2 N 1.5 ) (BP). B. Structured sparsity via GMs Compressible priors provide a natural launching point for incorporating further structure among the sparse signal coefcients. Here, by structure, we specically mean the probabilistic dependence and independence relationships among sparse signal coefcients as summarized by directed and undirected graphs. Such relationships are abundant in many diverse problems, such as speech recognition, computer vision, decoding of low-density parity-check codes, modeling of gene regulatory networks, gene nding and diagnosis of diseases. Graphical models also provide powerful tools for automatically learning these interactions from data. While learning GMs is an active research area, it is beyond the scope of this paper. 1) Tree graphs: Wavelet transforms sparsify piecewise smooth phenomena, including many natural and manmade signals and images. However, the signicant discrete wavelet transform (DWT) coefcients do not occur in arbitrary positions for such signals. Instead they exhibit a characteristic signal-dependent structure, with the large and small wavelet coefcients clustering along the branches of the wavelet tree. We highlight the persistency of the parent child relationship for several large DWT coefcients on the wavelet image in Figure 2. Hidden Markov trees (HMT) models and Gaussian scale mixtures (GSMs) on steerable pyramids succinctly and accurately captures this statistical structure [12, 20, 21]. The HMT models the probability 10

Original

Compressed

DWT-compressible image

DWT coefcients

Fig. 2.

10% of DWT coefcents

Shufed DWT coeff.

Most of the discrete wavelet transform (DWT) coefcients of natural images are small (blue in the bottom
row corresponds to zero amplitude). However, the signicant coefcients appear clustered on the wavelet trees [12, 20], as illustrated by the solid red lines. The dependence structure of the coefcients is crucial; by randomly shufing the DWT coefcients of the original image, we obtain a reconstruction that does not even remotely resemble a natural image, let alone the original.
density function of each wavelet coefcient as a mixture density with a hidden binary state that determines whether the coefcient is large or small. Wavelet coefcient persistence along the tree branches is captured by a tree-based Markov model that correlates the states of parent and children coefcients. GSMs exploit the Students t prior or its variants. Both models have been successfully applied to improve the performance of denoising, classication, and segmentation algorithms for wavelet sparse signals. For an explanation of the EM algorithm applied to GSMs, see the original EM paper [14]. Another Bayesian approach leverages the clustering of the DWT coefcients using the spike-and-slab prior along with VB inference. The main idea is to construct a tree-structured, conjugate-exponential family sparse model for wavelet coefcients where the mixture probability of the spike at an individual sparse coefcient on the wavelet tree is controlled by the size of its parent on the tree. Then, the VB updates can be efciently calculated with convergence guarantees. For instance, [17] demonstrates that the VB approach simultaneously improves both the recovery speed and performance over the state-of-the-art greedy and convex optimization based CS recovery approaches, discussed in Section II. Moreover, as 11

target

sparse recovery

LAMP recovery

Fig. 3.

LaMP Iter. #1

LaMP Iter. #2

LaMP Iter. #3

LaMP Iter. #4

LaMP Iter. #5

(Top) A real background subtracted image is shown where the foreground is sparse and clustered (blue
corresponds to zero). We represent the pixels on the image by an Ising model with hidden binary support variables s that are connected to their adjacent pixels over a lattice to explain clustered behavior. Exploiting this structure in sparse signal recovery leads to improved performance over the state-of-the-art for the same number of measurements. (Bottom) Reconstructing the Shepp-Logan phantom under 10dB measurement SNR with lattice matching pursuit (LAMP). N = = 104 , K = 1740, M = 2K = 3480.

i si + log(p(xi |si ))

1 y x 2 2
For the compressibility of the structured sparse signal x as signal dimensions vary, the pdfs p(xi |si ) should be chosen to result in a compressible prior for the signal coefcients, such as Students t, with proper scale parameters to differentiate the small and large coefcients. Although the objective function is non-convex, a local optimum can be efciently obtained via variational methods and alternating minimization techniques over the support and the signal coefcients. In the context of sparse signal recovery, recent work [18] exploits the Ising model and demonstrates that it naturally motivates a greedy search algorithm for background subtraction with clustered sparsity, dubbed Lattice matching pursuit (LAMP). Enabled by the Ising model, the LAMP algorithm (i) converges signicantly faster due to the reduction in the search space and (ii) recovers sparse signals from a much smaller number of measurements without sacricing stability. Similar optimization formulations can also be seen in applications involving face recognition in the presence of occlusions, where the occlusions are not only sparse but also contiguous. To solve (11), the LAMP algorithm relies on an approach inspired by the RIP assumption on the measurement matrices. The key observation for this iterative recovery scheme is that when the sampling matrix has K -RIP with constant
1 in (5), then the vector b = T y can serve as a rough
approximation of the original signal x. In particular, the largest K entries of b point toward the largest
K entries of the K -sparse signal x. Then, given the signal coefcient estimates, LAMP uses graph
cuts to obtain the MAP estimates of the latent support variables s. By clever book-keeping of the data 13

Fig. 4.

Incomplete

Lin. interp. (27.6dB)

IBP (35.2dB)

Learned dictionary

Natural images exhibit signicant self similarities that can be leveraged using the Indian buffet processes (IBP) in sparse
signal recovery even if a large number of pixels are missing. The IBP mechanism automatically infers a dictionary, in which the image patches are sparse, and the composition of these patches on the image to signicantly improve the recovery performance over linear interpolation.
residual along with the auxiliary support estimates, LAMP iteratively renes its signal estimates until convergence; see Figure 3 for a robust recovery example from M = 2K , where the signal-to-noise ratio (SNR) in measurements is 10dB. 3) Structured power-law processes: In many sparse signal recovery problems, the appropriate signal sparsifying basis or dictionary is oft-times unknown and must be determined for each individual problem. In dictionary learning problems, researchers develop algorithms to learn a sparsifying dictionary directly from data using techniques where a set of signals are compressible in particular with nonparametric Bayesian priors. By nonparametric, we mean that the number of parameters within the prior distribution is beforehand unspecied. Recent work in this area focused on vision applications and developed structured random processes to capture the power-law distribution of the image patch frequencies and segment sizes. Such distributions lay the foundations of a scale, resolution independent inference mechanism, which is key for compressible structured sparse models. We highlight two examples. Indian buffet processes (IBP), which provide exchangeable distributions over binary matrices, exploit hierarchical probability models and can be used to infer the dictionary size and its composition for natural images. Recent work exploits the IBP formalism for sparse signal recovery by jointly learning the sparsifying dictionary and demonstrates that signicant improvements can be achieved in sparse recovery, denoising, and inpainting of natural images [22]; see Figure 4. Similarly, Pitman-Yor processes provide a statistical framework for unsupervised discovery and segmentation of visual object categories with power-law properties. Further applications of such power-law priors to the sparse signal recovery problem are yet to emerge [23]. IV. G RAPHICAL MODELS FOR STRUCTURED MEASUREMENTS While random matrices have information preserving guarantees for the set of sparse signals, they are difcult to store, implement in real-hardware, and are computationally costly in sparse signal recovery. 14

(a) A bipartite graph. Fig. 5.

(b) Expansion.

An example of a bipartite graphs G = (A, B, E), over the left set A of size N and the right set B of size M. A
graph is an expander if any small subset S of A has many neighbors (S) in B.
Hence, in this section, we focus on another use of graphical models, to design high-performance measurement matrices that are sparse. Specically, we consider matrices whose entries are mostly equal to zero, while the non-zero entries are equal to 1.1 Each such matrix can be interpreted as bi-partite graph
G = (A, B, E) between a set A = {1. N } of N nodes, and a set B = {1. M } of M nodes: the
edge i j is present in the graph if and only if j,i = 1. Note that the nodes in A correspond to the coordinates of the signal x, while the nodes in B correspond to coordinates in the measurement vector
y. See Figure 5 for an illustration.
Sparse measurement matrices have several desirable features: (i) matrix-vector products during the encoding of the vector x into x can be performed very efciently, in time proportional to the number of non-zeros in ; (ii) the measurement vector x can be quickly updated if one or a few of its coordinates are modied crucial for processing massive data streams; (iii) the recovery process is quite efcient as well, since it relies on the matrix-vector product as a subroutine. Moreover, the graphical interpretation of such matrices enabled designing recovery algorithms using the belief propagation approach, leading to highly accurate recovery methods. Because of these reasons, various forms of sparse recovery using sparse matrices has been recently a subject of extensive research; see the recent survey [2] and the references therein. To complement the above, we also point out some disadvantages of sparse matrices. One of them is that they are directly applicable only to the case where the signal x is approximately sparse in the
Some of the constructions (e.g., [24]) allow the non-zero values to be equal to 1 as well.
canonical basis, i.e., x = (see the introduction for the notation). If the signal (as it is often the case) is sparse only after applying a linear transformation , then the actual measurement matrix is equal to
. This requires that the matrix is known before the measurements are taken. Note that the product
matrix might not be sparse in general, and the encoding therefore must perform extra computation, corresponding to matrix multiplication; the order of these computations is O(N M ) for general matrices, but it is much lower for special bases, such as discrete Fourier and wavelet transforms. A. Intuition and the randomized case We start from an intuitive overview of why properly chosen sparse matrices are capable of preserving enough information about sparse signals to enable their recovery. We focus on the case where x is exactly K -sparse, the matrix is random, and the goal is to exactly recover x from y = x with high probability. Consider rst a particularly simple distribution over sparse matrices, where the i-th column of contains exactly single 1, at a position, indexed by h(i), chosen independently and uniformly at random among the rows {1. M }. Multiplying by x has then a natural message-passing interpretation; each coordinate xi is sent to the h(i)-th coordinate of the measurement vector y , and all coordinates sent to a given entry of y are added together. Assuming that M is sufciently larger than K , we make the following observation: since the vector x is K -sparse and the indices h(i) are chosen randomly from

{1. M }, there is only a small probability that any particular coordinate xi will collide with any other
non-zero entry xi (where by collision we mean h(i) = h(i )). Therefore, xi = y h(i) and we can recover sparse coefcients by inverse mapping from the measurement vector. Unfortunately, the above procedure also creates many erroneous entries over the entire vector x. In short, we note that each zero entry xi has approximately K/M chance of colliding with some non-zero entry. Each such collision results in a erroneous non-zero entry in the recovered vector. As a result, a recovered vector can have K/M (N K) approximation of a K -sparse signal x. To improve the quality of recovery, we reduce the probability of such erroneous entries via repetition. Specically, instead of having only one 1 per column of the measurement matrix , we can select D random entries of each column and set them to 1.2 In the graph representation, this means that each node i A has a set of D neighbors in B ; we denote this set by (i). On one hand, this increases
K erroneous entries, and therefore becomes a poor
There are several different distributions of D-tuples from {1. M } than can be used, leading to essentially identical recovery
results; see the survey [2].
the probability of a collision, since now y can contain up to DK non-zero entries. However, if we set
M = CDK for some constant C > 1, then for any xed node i A, each of the D neighbors of i has
at most DK/M = 1/C chance of colliding with another non-zero entry. Therefore, the probability that all neighbors of i collide with other non-zero entries is very small, at most 1/C D. Therefore, a sparse matrix can potentially preserve information for an overwhelming fraction of the coordinates of x by encoding it into y. Then, how can we recover x from y ? If C > 2 and D = d log N for large enough constant d, then one can show that, with high probability, less than half of the neighbors of each node i A collide with other non-zero entries. In that case, taking the median or the mode (the most frequently occurring value) of the entries {y j : j (i)} returns the correct value of xi. This is the basic idea behind Count-Median [25] and Count-Sketch [24] algorithms, which further extend this approach to general vectors x.3 The resulting algorithms require M = O(K log N ), and the recovery is performed in time proportional to O(N log N ). In order to reduce the number of measurements, the researchers have developed more elaborate algorithms, based on loopy belief propagation [26, 27] and related message-passing approaches [28]. Here, we sketch the Counter Braids algorithms of [27]. That algorithm works assuming that the vector

(S) = iS (i). We say that the graph G is an (s, )-expander if for any S A, |S| s, we have |(S)| |S|. Note that the expansion factor is always at most D, since each node can have at most D neighbors. However, there exist graphs that achieve = (1 )D for any constant > 0; such graphs
require D = O(log(N/s)) and M = |B| = O(s log(N/s)). See Figure 5 for an illustration. To see why expansion is desirable for sparse recovery, consider the case when is very close to 0 and
s = K. Let x be a K -sparse vector , and let S be a set of indices of non-zero entries in x. Then we
observe that for most nodes i S , only a small fraction of their neighbors (i) collide with any other non-zero entry. Such entries xi can be thus recovered correctly by the median-based procedure outlined earlier. To recover all entries, we can use an iterative renement approach, similar to the one from the previous section, and inspired by the bit-ipping algorithm for decoding low-density parity check codes. Consider rst the case where x is exactly K -sparse. The algorithm [30] starts by setting an initial approximation
x to 0 and iteratively renes x in order to achieve x = y. In each step, it tries to reduce x y 0 ,
by nding a pair (i, g) such that incrementing xi by g reduces the
difference. It is then shown that
if the graph is an (O(K), (1 )D)-expander for a sufciently small value of , then x converges to x in O(K) iterations. The running time of the algorithm is dominated by the preprocessing step, which takes time O(N D), after which each iteration can be performed in O(log N ) time or, in some cases, even faster. Since the graph G is an expander, it follows that the number of measurements is
M = O(KD) = O(K log(N/K)).
When x is not exactly K -sparse, then the
norm is no longer a suitable measure of progress, and
we need to use a more rened approach. To this end, we rst observe that the graph-theoretic notion of expansion has a natural and useful geometric interpretation. Specically, consider the following variant of the K -RIP in (5): we say that an M N matrix has the K -restricted isometry property in the norm (K -RIP1) with constant , if for all K -sparse vectors x, we have

x 1 (1 ) x

It has been shown in [31] that if is a matrix underlying a (K, D(1 /2))-expander, then /D satises K -RIP1 with constant. As a result, both
minimization and variants of the iterative algorithms
described in Section II can be used for sparse matrices. Unlike the methods using the standard RIP, the algorithms produce x which satises a somewhat weaker guarantee of the form

C x xK

Perhaps surprisingly, the simplest of the algorithms, called Sequential Sparse Matching Pursuit [32], is similar to the aforementioned algorithm of [30]. There are two key differences though. Firstly, each iteration reduces not the

error x y 0 , but the

error x y 1. This is because by the RIP1

property, the error x x

is small when x y
is small. Second, in order to be able to apply the
RIP1 property, we need to ensure that the vector x continues to be O(K)-sparse after we perform the updates. Since this property might cease to be true after some number of steps, we need to periodically re-sparsify the vector x by setting to zero all but the K largest (in absolute value) entries of x. This re-sparsication step is a standard tool in the design of iterative recovery algorithms for general vectors
See the survey [2] for a more detailed description of the algorithms for sparse matrices. V. C ONCLUSIONS A great deal of theoretic and algorithmic research has revolved around sparsity view of signals over the last decade to characterize new, sub-Nyquist sampling limits as well as tractable algorithms for signal recovery from dimensionality reduced measurements. Despite the promising advances made, real life applications require more realistic signal models that can capture underlying, application dependent order of sparse coefcients, better sampling matrices with information preserving properties that can be implemented in practical systems, and ever faster algorithms with provable recovery guarantees for real-time operation. On this front, we have seen that graphical models (GM) are emerging to effectively address the core of many of these desiderata. GMs provide a broad scaffold for automatically encoding the probabilistic 19
dependencies of sparse coefcients for sparse signal recovery. By exploiting the GM structure of signals beyond simple sparsity, we can radically reduce the number of measurements, increase noise robustness, and decrease recovery artifacts in signal acquisition. GMs are instrumental in constructing measurement matrices based on expander graphs. These matrices not only stably embed sparse signals into lower dimensions but also lead to faster recovery algorithms with rigorous guarantees. Moreover, the GMbased inference tools, such as variational methods, can estimate a posterior distribution for the sparse signal coefcients, providing condence bounds that are critical in many applications. To date, the sparse signal acquisition and recovery problemssurprisinglyhave been studied largely in isolation. Real progress in efcient signal recovery, processing and analysis requires that we unify probabilistic, structured sparsity models with sparse measurement matrices to simultaneously reduce sampling requirements and the computational complexity of recovery without compromising the recovery guarantees. This will in turn entail investigation of streaming algorithms, coding theory, and learning theory with a common, connecting element, which we expect to be graphical models. R EFERENCES

[1] R. G. Baraniuk, V. Cevher, and M. Wakin, Low-dimensional models for dimensionality reduction and signal recovery: A geometric perspective, Proceedings of the IEEE, 2010. [2] A. Gilbert and P. Indyk, Sparse recovery using sparse matrices, Proceedings of IEEE, 2010. [3] C. M. Bishop, Pattern recognition and machine learning. Springer, 2006. [4] D. L. Donoho, Compressed sensing, IEEE Trans. Info. Theory, vol. 52, pp. 12891306, Sept. 2006. [5] E. J. Cand` s, Compressive sampling, in Proc. International Congress of Mathematicians, vol. 3, (Madrid, Spain), e pp. 14331452, 2006. [6] A. Cohen, W. Dahmen, and R. DeVore, Compressed sensing and best k-term approximation, American Mathematical Society, vol. 22, no. 1, pp. 211231, 2009. [7] S. L. Lauritzen, Graphical Models. Oxford University Press, 1996. [8] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, An introduction to variational methods for graphical models, Machine Learning, vol. 37, no. 2, pp. 183233, 1999. [9] A. Willsky, Multiresolution Markov models for signal and image processing, Proceedings of the IEEE, vol. 90, no. 8, pp. 13961458, 2002. [10] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1988. [11] D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009. [12] M. S. Crouse, R. D. Nowak, and R. G. Baraniuk, Wavelet-based statistical signal processing using Hidden Markov Models, IEEE Trans. Signal Processing, vol. 46, pp. 886902, Apr. 1998. [13] J. S. Yedidia, W. T. Freeman, and Y. Weiss, Generalized belief propagation, Advances in Neural Information Processing Systems, vol. 13, pp. 689695, 2001. [14] A. P. Dempster, N. M. Laird, and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological), vol. 39, no. 1, pp. 138, 1977.
[15] V. Cevher, Learning with compressible priors, in NIPS, (Vancouver, B.C., Canada), 712 December 2008. [16] S. Negahban and M. J. Wainwright, Estimation of (near) low-rank matrices with noise and high-dimensional scaling, Arxiv preprint arXiv:0912.5100, 2009. [17] L. He and L. Carin, Exploiting structure in wavelet-based Bayesian compressive sensing, 2008. Preprint. Available at http://people.ee.duke.edu/ lcarin/Papers.html. [18] V. Cevher, M. F. Duarte, C. Hegde, and R. G. Baraniuk, Sparse signal recovery using Markov random elds, in Neural Information Processing Systems (NIPS), (Vancouver, B.C., Canada), 811 December 2008. [19] I. Daubechies, R. DeVore, M. Fornasier, and C. S. Gunturk, Iteratively Reweighted Least Squares Minimization for Sparse Recovery, Communications on Pure and Applied Mathematics, vol. 63, pp. 00010038, 2010. [20] J. K. Romberg, H. Choi, and R. G. Baraniuk, Bayesian tree-structured image modeling using wavelet-domain Hidden Markov Models, IEEE Trans. Image Processing, vol. 10, pp. 10561068, July 2001. [21] M. J. Wainwright and E. P. Simoncelli, Scale mixtures of Gaussians and the statistics of natural images, in Neural Information Processing Systems (NIPS) (S. A. Solla, T. K. Leen, and K.-R. M ller, eds.), vol. 12, (Cambridge, MA), u pp. 855861, MIT Press, Dec. 2000. [22] M. Zhou, H. Chen, J. Paisley, L. Ren, G. Sapiro, and L. Carin, Non-parametric bayesian dictionary learning for sparse image representations, in Neural Information Processing Systems (NIPS), 2009. [23] E. B. Sudderth and M. I. Jordan, Shared segmentation of natural scenes using dependent Pitman-Yor processes, in Advances in Neural Information Processing Systems, vol. 21, 2009. [24] M. Charikar, K. Chen, and M. Farach-Colton, Finding frequent items in data streams, Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), 2002. [25] G. Cormode and S. Muthukrishnan, Improved data stream summaries: The count-min sketch and its applications, Proceedings of Latin American Theoretical Informatics Symposium (LATIN), 2004. [26] D. Baron, S. Sarvotham, and R. G. Baraniuk, Bayesian compressive sensing via belief propagation, to appear in IEEE Transactions on Signal Processing, 2010. [27] Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani, Counter braids: a novel counter architecture for per-ow measurement, in SIGMETRICS 08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, (New York, NY, USA), pp. 121132, ACM, 2008. [28] D. Donoho, A. Maleki, and A. Montanari, Message passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences, 2009. [29] C. Estan and G. Varghese, New directions in trafc measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems, 2003. [30] S. Jafarpour, W. Xu, B. Hassibi, and A. R. Calderbank, Efcient and robust compressed sensing using high-quality expander graphs, IEEE Transactions on Information Theory, vol. 33(9), 2009. [31] R. Berinde, A. Gilbert, P. Indyk, H. Karloff, and M. Strauss, Combining geometry and combinatorics: A unied approach to sparse signal recovery, in Proc. Allerton Conf. Communication, Control, and Computing, 2008. [32] R. Berinde and P. Indyk, Sequential sparse matching pursuit, Proceedings of Allerton Conference on Communication, Control, and Computing, 2009.

Type: Heavy-lift

CH-47D Chinook
twin 3-bladed tandem main rotors twin seat side-by-side cockpit inside glazed nose long rectangular fuselage (bulging along lower sides), elevated front and rear engine housings external engine nacelles on rear sides of fuselage rear hinged loading ramp to cargo hold fixed 4-wheeled undercarriage
Type: Medium-lift tilt-rotor

MV-22 Osprey

distinctive twin 3-bladed tilt-rotors and rounded hub spinners high-wing configuration with short wing sections supporting large tilt rotor engine nacelles at tips rounded square-section flat bottomed fuselage, with large bulging underwing sponsons short rounded nose section, sideby-side cockpit arrangement under single rounded canopy, nose-mounted mini radome and forward projecting refuelling probe rear sloping fuselage section rising to distinctive flattened and curved rear tail boom supporting twin finned tail plane with hinged loading ramp to cargo hold under squat retractable tricycle undercarriage

CH-53E Super Stallion

large 7-bladed main rotor with flattened circular hub cap, canted 4-bladed tail rotor broad and long rounded square sectioned fuselage sloping up to short tail boom with flattened underside, sharply canted tail fin with distinctive cranked sidemounted tail plane rounded engine housing tapering along upper fuselage, large outboard tubular air intakes with conical intake filters, large angled circular exhaust tubes to rear large curved sponsons at centre section with projecting outer supports for large droptanks distinctive rounded flat nose section incorporating cockpit nose glazing and forward projecting refuelling probe rear hinged loading ramp to cargo hold squat semi-retracting tricycle undercarriage

USA COMBAT AIRCRAFT

Type: Close air support

A-10A Thunderbolt

low-wing, square leading and trailing edge with upward canted outer sections and down-turned wing-tips, projecting fairings over main landing gear short nose with up-front cockpit arrangement twin fin assembly large pair of circular engine nacelles mounted on upper rear fuselage many under-wing weapon hard points and large nose mounted cannon semi-retractable tricycle undercarriage

Armament: q 30mm cannon

AIM-9M Sidewinder IR guided air-to-air missiles LAU-69/A unguided rockets
Game notes: q radar symbol:
ground radar priority: medium

Type: Multi-role fighter

F-16 Fighting Falcon
mid-wing, swept leading edge, square trailing edge, wings blended to fuselage long bubble-shaped canopy and short sharp nose single large curved air intake under nose single large tail fin, downward canted all-moving tail plane wing-tip missile mounts, under-wing hard-points retractable tricycle undercarriage
AIM-9M Sidewinder IR guided air-to-air missiles AIM-120 AMRAAM radar guided air-to-air missiles AGM-65D Maverick IR guided air-to-surface missiles

chaff flares Game notes:

Type: Carrier-borne attack

AV-8B Harrier

high-wing, swept leading and trailing edges, sharp downward cant swept tail fin, downward canted all-moving tail plane compact bulbous fuselage with rounded main air intakes immediately aft of either side of cockpit short nose with up-front cockpit arrangement thrust vectoring nozzles under wings on either side of fuselage under-wing hard-points, underfuselage bulging cannon housing retractable main landing gear with under-wing retractable stabilisers

Armament: q 25mm cannon

Type: Carrier-borne interceptor

F/A-18 Hornet

mid-wing, swept leading edge extended into hood along forward fuselage, square trailing edge long slender nose section and canopy, with wings centered well aft of fuselage center line swept all-moving tail plane well aft of tall sharply canted twin tail fins engine intakes either side of fuselage under wing leading edge, closely-spaced rear nozzles under-wing and fuselage hard-points with wing-tip missile mounts retractable tricycle undercarriage
AIM-9M Sidewinder IR guided air-to-air missiles AIM-120 AMRAAM radar guided air-to-air missiles AGM-65F Maverick IR guided air-to-surface missiles Game notes:

USA TRANSPORT AIRCRAFT

C-130J Hercules II
4 propfan engines on under-wing engine nacelles, distinctive sabre-like 6-bladed propellers broad high-wing configuration with square leading edge blending to fuselage distinctive broad tail plane and tall round-topped tail fin arrangement large circular-sectioned fuselage rising to broadly flattened and tapered tail boom at rear, rounded bulging sponsons to lower underwing section short rounded up-turned nose below broad rounded cockpit section with distinctive wraparound glazing large hinged cargo doors to rear under sloping tail underside retractable undercarriage with 4 fixed main wheels and twin steerable nose wheels no under-wing fuel tanks as per earlier Hercules variants

C-17 Globemaster III

4 stout turbo-fan engines mounted on large forward-projecting underwing pylons with large circular metallic air intakes and conical exhaust outlets to rear distinctive swept high-wing configuration, large downward sloping tapered wings ending in up-turned swept winglets, large underwing deflection flaps and rearward projecting supporting fins huge circular-section main fuselage, bulging over wing junction, rear raised bulging tail section tapering to rounded point at rear, flattened underside at hinged cargo door area large underwing sponsons, smoothly blended to mid fuselage and angling outwards at base, rounding back into fuselage underbelly large distinctive swept T-tail configuration smoothly rounded tapering nose section with wrap-around glazed cockpit retractable undercarriage with 12 fixed main wheels arranged in 4 triplets at rear and twin steerable nose wheels

USA ARMORED VEHICLES

Type: Main battle tank

M1A2 Abrams

tracked - 7 road wheels plus drive sprocket and idler on either side long low flat-sided hull, flat raised rear section behind turret, flattened rear end with engine louvres and circular lamp housings large angular low profile turret topped by small thermal sighting turret and large hatch-mounted MG with stowage racks to rear long high calibre main gun barrel overhangs hull front Game notes: q radar symbol:

q q q q q q

Armament: q 120mm gun Decoys: q smoke grenades

12.7mm machine gun

ground radar priority: medium surface-to-air ceiling 1,000m surface-to-air range 2,000m armored night vision equipment
Type: Infantry fighting vehicle

M2A2 Bradley

Recognition features: q tracked - 6 road wheels plus drive sprocket and idler on either side
angular high-sided hull, sloping front and port-side inset drivers hatch, flattened rear end with troop compartment loading ramp and large projecting stowage bins on either side small angular turret with secondary armor panels to rear, short low caliber main gun barrel and side mounted flip-up TOW launcher
radar symbol: ground radar priority: high surface-to-air ceiling 2,000m surface-to-air range 4,000m armored night vision equipment

M220 TOW2B tube-launched optically-tracked wire-guided missiles

Decoys: q smoke grenades

Type: Armored personnel carrier

M113A2

tracked - 5 road wheels plus drive sprocket and idler on either side high-sided box-shaped hull, backward sloping front and flattened rear end with loading ramp to troop compartment hatch mounted MG on hull topside (no turret) Game notes: q radar symbol:

q q q q q

ground radar priority: high surface-to-air ceiling 1,000m surface-to-air range 2,000m armored night vision equipment

Type: Scout car

M1025 HMMWV (HumVee)
high 4-wheeled chassis distinctive flat-sided wide and low-profiled body, square front, slightly sloping bonnet, vertical windshield, downward slope at rear end of cab roof roof-mounted MG Game notes:
radar symbol: ground radar priority: low
USA SELF-PROPELLED ARTILLERY
Type: Artillery (howitzer)

M109A2 (155mm)

tracked - 7 road wheels plus drive sprocket and idler on either side, no side-skirts over tracks wide angular hull with bevelled nose section and downward sloping top at front, flattened rear with hull access door and stowed entrenching spades large flat-topped turret centered aft with sloping curved front and flat sides, thermal sighting turret and hatch-mounted MG atop, flattened rear end with projecting stowage box and racks very long high caliber main gun extending well forward of hull front with large open-sided muzzle

q q q q

155mm howitzer
Type: Multiple rocket systems

M270 MLRS (227mm)

Recognition features: q tracked - 6 road wheels plus drive sprocket and idler on either side, no side-skirts over tracks q box-shaped cab section at front with backward sloping front-face and protective louvres over windows, rear flatbed platform for launcher q large box-shaped turret-mounted multiple rocket launcher stowed horizontally at rear, turned and pitched to firing position Armament: q 227mm rockets

USA AIR DEFENSE VEHICLES

Type: AAA

M163 Vulcan

tracked - 5 road wheels plus drive sprocket and idler on either side high-sided box-shaped hull, backward sloping front with bulged section, box-shaped bulges along upper sides, flattened rear end small circular turret with sloping sides and flat open top, small side-mounted radar dish, distinctive multi-barrelled cannon on pivoting skeleton mount

20mm cannon

ground radar priority: high surface-to-air ceiling 1,000m surface-to-air range 2,000m armored night vision equipment range-only radar

Type: SAM

M1037 Avenger
Recognition features: q high 4-wheeled chassis
distinctive flat-sided wide and low-profiled body, square front, slightly sloping bonnet, vertical windshield to cut-short cab, flatbed launcher platform to rear platform-mounted box-shaped sloping-top turret with pivoting side-mounted rectangular rocket launchers Game notes:
FIM-92A Stinger IR guided surface-to-air missiles
radar symbol: ground radar priority: high surface-to-air ceiling 3,000m surface-to-air range 5,000m night vision equipment

M48A1 Chaparral

tracked - 5 road wheels plus drive sprocket and idler on either side box-section hull with sloping front, raised rectangular forward cab section and flatbed launcher platform to rear platform-mounted flat-sided curved roof turret on circular base with Chaparral missile pairs mounted on either side Game notes: q radar symbol:
Armament: q Chaparral IR guided surface-to-air missiles
ground radar priority: high surface-to-air ceiling 3,000m surface-to-air range 5,000m night vision equipment FLIR

USA TRANSPORT VEHICLES

Type: Light 4x4 vehicle

M998 HMMWV (HumVee)

distinctive flat-sided wide and low-profiled body, square front, slightly sloping bonnet, vertical windshield to cut-short cab, flatbed cargo area to rear
Type: Utility vehicle (truck)

M923A1 Big Foot

high 6-wheeled truck chassis - 2 wheels in front, 4 at rear large flat radiator grille with integral headlights, flat tapering bonnet, box-shaped cab with vertical windshield, angled mud guards over front wheels high sided canvas covered cargo area to rear Game notes: q radar symbol:
ground radar priority: low

Type: Fuel tanker

M978 (HEMTT)
Recognition features: q high 8-wheeled chassis - 2 pairs of 4 wheels
distinctive forward-projecting cab with steeply angled large flat windshield and underside, narrow rectangular section behind cab with side-mounted spare wheel large curved-sided flat-topped fuel tank to rear and adjoining downward angled curved rear end section Game notes:

USA WARSHIPS

Type: Amphibious assault ship

Tarawa Class

wide and high-sided box-section hull, long bow, square stern section continuous flight deck port side outboard aircraft lift, stern inboard aircraft lift, large stern water-line loading door long narrow rectangular starboard side superstructure, large forward-mounted lattice mast and aft-mounted structures atop two storey bridge large deck-side crane Game notes: q radar symbol:

Armament: q 25mm cannons

ground radar priority: high surface-to-air ceiling 5,000m surface-to-air range 1,0000m air search radar
Sea Sparrow radar guided surface-to-air missiles

Type: Frigate

Oliver Hazard Perry Class
Recognition features: q slender low-profile hull with sharp high-sided bow, square inward sloping shallow stern
long high-sided box-section superstructure forward raised bridge section, small spherical radome atop tall central lattice mast with large outboard aerials, shorter forward mast with large rectangular radar dish atop small forward deck gun position on circular base aft deck-level helicopter landing pad
radar symbol: ground radar priority: high surface-to-air ceiling 5,000m surface-to-air range 10,000m air search radar

Armament: q 76mm guns

SM-1MR Standard radar guided surface-to-air missiles

Type: Landing craft

Tarawa Landing Craft
flat rectangular hull with squarely angled-in bow and stern, raised gusseted sides to cargo deck hinged bow loading ramp, twin crane booms astern narrow box-shaped superstructure on starboard side cargo deck, single pole-mounted radar antenna Game notes: q radar symbol:

Type: Hovercraft

Recognition features: q rectangular flat-bed hull, widely projecting all-round inflatable skirt with square corners
long and narrow deck-side superstructures with top-mounted engine intakes/exhausts hinging bow and stern loading ramps prop-shafts to aft-mounted twin 5-bladed propellers in circular enclosures with rudder planes attached Game notes:

RUSSIAN COMBAT HELICOPTERS

Mi-28N Havoc-B

5-bladed main rotor with spherical radome, 4-bladed X shaped tail rotor tandem stepped separate cockpit arrangement nose-mounted radome with FLIR turret underneath rounded engine nacelles with downward pointing rearward exhaust outlets stub-wings (downward sloping) with pylons and wing-tip ECM pods chin-mounted cannon turret with ammo panniers asymmetrical tail plane arrangement fixed undercarriage and tail wheel
Armament: q 30mm cannon (both armour piercing and high explosive rounds) q Igla-V IR guided air-to-air missiles q Ataka radio command guided anti-tank missiles
80mm unguided rockets 130mm unguided rockets GSh-23L 23mm cannon pods

Chaff Flares

Ka-50 Hokum
twin 3-bladed co-axial main rotors (no tail rotor), mast-mounted 'mini' radome single seat cockpit with angular flat armor glass canopy narrow angular cockpit section blending to smoothly sharpened nose section with chin-mounted fixed sight on flattened underside, rounded square-section tail boom with even taper to point at rear rounded engine nacelles each side of upper fuselage immediately aft of cockpit, domed dust filters to air intakes distinctive tail configuration angular tail fin and tail plane with endplate fins enlarged stub wings with weapons pylons and wing tip ECM pods side-mounted 30mm cannon retractable tricycle undercarriage
30mm cannon (both armor piercing and high explosive rounds) Igla-V IR guided air-to-air missiles Vikhr laser guided anti-tank missiles 80mm unguided rockets 130mm unguided rockets GSh-23L 23mm cannon pods

Ka-52 Hokum-B

twin 3-bladed co-axial main rotors (no tail rotor), mast-mounted 'mini' radome twin seat side-by side cockpit with flat armor windshield and curved 'gull-wing' style upward opening canopy doors smoothly sculpted forward fuselage section with rounded nose, rounded square-section tail boom with even taper to point at rear rounded engine nacelles each side of upper fuselage immediately aft of cockpit, domed dust filters to air intakes distinctive tail configuration angular tail fin and tail plane with endplate fins nose-mounted cylindrical FLIR turret, spherical SAMSHIT turret above cockpit rear enlarged stub wings with weapons pylons and wing tip ECM pods side-mounted 30mm cannon retractable tricycle undercarriage Decoys:

Armament: q 30mm cannon (both armor piercing and high explosive rounds)
Igla-V IR guided air-to-air missiles Vikhr laser guided anti-tank missiles 80mm unguided rockets 130mm unguided rockets GSh-23L 23mm cannon pods

Mi-24D Hind

5-bladed main rotor, 3-bladed tail rotor tandem stepped cockpits with domed canopies tall and narrow appearance to main fuselage hinged loading doors on either side of main cabin IR suppressors fitted to engine exhaust outlets sharply downward angled stub wings with weapons pylons and down turned wing-tips chin-mounted gun-turret and sight/radar mounts retractable tricycle undercarriage
12.7mm Gatling gun AT-6 Spiral radio command guided anti-tank missiles 57mm unguided rockets 80mm unguided rockets

flares Game notes:

Ka-29 Helix-B
twin 3-bladed co-axial main rotors (no tail rotor) twin seat side-by-side cockpit short rectangular section fuselage with distinctive flat nose and tail plane with endplate fins hinged loading doors on either side of main cabin weapon pylons supported on outboard racks fixed 4-wheeled undercarriage with main gear outboard of fuselage sides
Armament: q 57mm unguided rockets

80mm unguided rockets

RUSSIAN TRANSPORT HELICOPTERS

Mi-17 Hip

5-bladed main rotor and 3-bladed tail rotor twin seat side-by-side cockpit inside glazed nose long rounded main fuselage and slender tail boom rear fuselage has clam shell cargo hold doors IR suppressor fitted to engine exhaust outlets weapon pylons supported on outboard racks fixed tricycle undercarriage with outboard struts supporting main wheels

Mi-6 Hook

5-bladed main rotor and 4-bladed tail rotor twin seat side-by-side cockpit aft of glazed observers station in nose extremely long rounded main fuselage section with shorter tail boom large wings, tail plane and external fuel tanks rear fuselage has clam shell cargo hold doors fixed tricycle undercarriage with outboard struts supporting main wheels

RUSSIAN COMBAT AIRCRAFT

Su-25 Frogfoot
high-wing, swept leading edge, square trailing edge, wing-tip pods single tall tail fin with smaller aft upward canted tail plane on aft projecting boom short sloping nose and canopy, flattened fuselage sides and bottom, rounded engine nacelles with aft projecting circular outlets many under-wing weapon hard points and large nose mounted cannon fully retractable tricycle undercarriage
30mm cannon AA-8A Aphid IR guided air-to-air missiles 80mm unguided rockets

Mig-29 Fulcrum

low-wing, swept leading and trailing edges, wings blended to fuselage all-moving swept tail plane and canted twin tail fins downward-pointing nose, humped-back fuselage aft of cockpit tapering to flattened projecting fish-tail section at rear, flattened fuselage underside separated under-fuselage engine nacelles with canted and angled rectangular air intakes and widely spaced rear nozzles under-wing hard points and side-mounted cannon retractable tricycle undercarriage

30mm cannon AA-10A Alamo radar guided air-to-air missiles AA-10B Alamo IR guided air-to-air missiles AA-11 Archer IR guided air-to-air missiles AS-10 Karen IR guided air-to-surface missiles Game notes:

Yak-41 Freestyle

high-wing, swept leading edge, square trailing edge with slight sweep along outer section, wing-tip pods compact square-sided fuselage with angled side air intakes and short nose with up-front cockpit distinctive twin tail booms and canted fins, cutaway for extendable thrust vectoring engine nozzle under-wing hard-points retractable tricycle undercarriage
AA-8A Aphid IR guided air-to-air missiles 80mm unguided rockets

Su-33 Flanker

low-wing, swept leading and trailing edge, blended to fuselage, swept canard foreplanes downward angled forward fuselage with enlarged bulbous nose section, humped-back central fuselage tapering to flattened projecting tail-sting at rear swept tail plane and twin vertical tail fins separated under-fuselage engine nacelles with canted and angled rectangular air intakes and large widely spaced rear nozzles under-wing and fuselage hard-points with wing-tip missile mounts retractable tricycle undercarriage
30mm cannon AA-8A Aphid IR guided air-to-air missiles AA-8B Aphid radar guided air-to-air missiles AA-10A Alamo radar guided air-to-air missiles AA-10B Alamo IR guided air-to-air missiles AS-14 Kedge laser guided air-to-surface missiles Game notes:
RUSSIAN TRANSPORT AIRCRAFT

An-12B Cub

4 turboprop engines with 4-bladed propellers on under-wing nacelles high-wing configuration with swept leading edge and downward canted wing tip sections large angled tail fin incorporating tail gun turret, tail plane set well aft large circular-sectioned fuselage tapering to broadly flattened tail boom at rear, rounded sponsons to lower fuselage center section smoothly rounded nose section tapering to glazed observation turret below wrap-around cockpit glazing, chin-mounted radome feature large inward hinging cargo doors to rear under sloping tail underside retractable undercarriage with 4 fixed main wheels arranged 2 pairs at rear and twin steerable nose wheels

IL-76MD Candid

4 large slender turbo-fan engines mounted on forward-projecting under-wing pylons with 'clam shell' thrust reversing exhaust outlets to rear swept high-wing configuration, large downward sloping tapered wings with large underwing flaps and projecting supporting fins large slender circular-section main fuselage bulging at wing junction, gently upward curving tail section tapering to rear tail gun turret, with large rear hinged loading ramp to cargo hold curved sponson arrangement on lower central fuselage with additional main undercarriage pod on underbelly swept T-tail configuration with large forward rectangular sectioned projection atop distinctive smoothly rounded tapering nose section incorporating glazed observation station, large radome section and wrap-around glazed cockpit retractable undercarriage with 16 fixed main wheels arranged on 4 axles at rear and 4 co-axial steerable nose wheels

RUSSIAN ARMORED VEHICLES

tracked - 6 road wheels plus drive sprocket and idler on either side long and low flat-sided hull with front and rear splashers curving down over track ends, front top-side of hull slopes down between side-skirts, distinctive pair of fuel barrels mounted on rear distinctive low circular domed turret with hatch mounted MG and stowed snorkel on brackets at rear long high calibre main gun barrel overhangs hull front
q 12.7mm machine gun 125mm gun AT-11 Sniper laser beam riding anti-tank missiles
Decoys: q smoke grenades Type:Infantry fighting vehicle
angular low-profile hull with sloping underside and sharply pointed leading edge, flattened rear with bulged access doors, curved-ended splashers to tracks projecting along sides small circular turret with sloping sides and flat top offset to aft, long slender low calibre main gun barrel and turret mounted tubular missile launcher
30mm cannon AT-5 Spandrel radar guided anti-tank missiles
tracked - 6 road wheels plus drive sprocket and idler on either side high-sided box shaped hull, sloping underside to front with pointed leading edge and flattened rear end, troop compartment main access doors on rear topside and rear end of hull small circular flat-topped turret, high caliber main gun barrel with box-shaped laser sight mounted over base and side-mounted co-axial cannon
100mm gun q 30mm cannon AT-10 Stabber laser beam riding anti-tank missiles

smoke grenades

BTR-80
Recognition features: q high 8-wheeled chassis, 2 pairs of 4 wheels
angular long narrow hull with sloping underside to front, flattened rear end and sloped upper sides with angular wheel arches below very small circular flat-topped MG mounted turret Game notes:

14.5mm machine gun

radar symbol: ground radar priority: medium surface-to-air ceiling 1,000m surface-to-air range 2,000m armored night vision equipment

BRDM-2

high 4-wheeled chassis angular small and narrow hull, sharp leading edge and sloping underside to front, sloping upper sides with curved wheel arches below, flattened rear end very small circular flat-topped MG mounted turret Game notes: q radar symbol:

Armament: q 14.5mm machine gun
RUSSIAN SELF-PROPELLED ARTILLERY

2S19 (152mm)

long and low flat-sided hull with front and rear splashers curving down over track ends, front top-side of hull slopes down between side-skirts very large high-sided box-shaped turret with hatch-mounted MG and distinctive rear-mounted SAM launcher tube very long high caliber main gun extending well forward of hull front
152mm howitzer 12.7mm machine gun

BM-21 Grad MRS (122mm)

high 6-wheeled truck chassis - 2 wheels at front, 4 at rear low wide radiator grille, smooth curved tapering bonnet and short upright cab with backward sloping windshield, vertical faced mud guards over front wheels with integral headlights, flatbed platform behind with launcher turret over rear axle box-shaped grouped rocket tubes stowed on turret at rear, turned and pitched to firing position Game notes: q radar symbol:
Armament: q 122mm rockets
RUSSIAN AIR DEFENSE VEHICLES

SA-13 Gopher

Recognition features: q tracked - 6 road wheels plus drive sprocket and idler on either side, no side-skirts
long low-profile flat-topped hull with tapering cab sides and sloping top/underside to front, box-shaped side-mounted stowage lockers along upper sides, flattened rear end centred circular turret mount for launcher arm with side-mounted box-section rocket launchers, stowed laid flat on hull top and pivoted on arm to firing position

q q q q q q q

radar symbol: ground radar priority: high surface-to-air ceiling 3,000m surface-to-air range 5,000m armored night vision equipment Flat Box passive radar
SA-13 Gopher IR guided surface-to-air missiles

Type: SAM/AAA

SA-19 Grison
tracked - 6 road wheels plus drive sprocket and idler on each side, no side-skirts box-section hull, downward sloping front, flattened and slightly inward sloping rear end long and narrow rectangular main turret section over-hanging circular turret base at rear, frontal radome mounting, curved rectangular radar dish mounted on elevated section at turret rear top twin-barreled cannon and quad SAM tubes mounted on either turret side Game notes: q radar symbol: q ground radar priority: high q surface-to-air ceiling 4,000m q surface-to-air range 8,000m q armored q night vision equipment q surveillance and tracking radar
Armament: q 4x30mm cannons
SA-19 Grison radio command guided surface-to-air missiles
RUSSIAN TRANSPORT VEHICLES

UAZ-469B

Recognition features: q high 4-wheeled chassis,
small compact appearance, distinctive rounded bonnet, headlights and radiator grille, backward sloping windshield, canvas roof

Ural-4320

high 6-wheeled truck chassis - 2 wheels in front, 4 at rear low wide radiator grille, smooth curved tapering bonnet and short upright cab with backward sloping windshield, vertical faced mud guards over front wheels with integral headlights high sided canvass covered cargo area to rear Game notes: q radar symbol:

Ural-4320 Fuel Tanker

Recognition features: q high 6-wheeled truck chassis - 2 wheels in front, 4 at rear
low wide radiator grille, smooth curved tapering bonnet and short upright cab with backward sloping windshield, vertical faced mud guards over front wheels with integral headlights squat flat-sided curved-topped fuel tank at rear Game notes:

RUSSIAN WARSHIPS

Kiev Class
slender hull with sharp raked bow profile and broad square front deck, angled square stern with stepped sunken aft deck sections large cylindrical missile launch tubes on forward deck angled flight deck overhangs port hull side large angular multi-leveled starboard side superstructure, tall lattice mast with spherical radome aft of main radar dish, large angular funnel to rear, side-mounted radomes numerous smaller radar sensors, missile launchers and gun turrets stowed pilot boats in aft hull recesses
30mm cannons q 76mm gun SA-N-3 Goblet radio command guided surface-to-air missiles radar symbol: ground radar priority: high surface-to-air ceiling 5,000m surface-to-air range 10,000m
Armament: q SA-N-4 Gecko radio command guided surface-to-air missiles

Krivak II Class

Recognition features: q slender low-profile hull, raked bow with curved front deck, low flat sunken aft deck with broad curve to stern q large box-shaped missile launcher on forward deck with angular canted blast shields to fore q broad rectangular forward superstructure with large squat lattice mast and radar dishes atop
low aft superstructure with squat rectangular funnel aft twin stepped gun turret arrangement
100mm guns SA-N-4 Gecko radio command guided surface-to-air missiles
long and wide high-sided hull with curved upper edge and rounded overhanging bow section over loading ramp below, high-sided all-round inflatable skirt with enlarged curved bulge under bow door twin forward-mounted gun turrets either side of bow low and wide forward bridge section with squat lattice mast to rear, large low square structure amidships aft mast-mounted twin pairs of face-to-face 4-blade propeller sets forward of tall twin tail fins/rudders
ground radar priority: high surface-to-air ceiling 1,000m surface-to-air range 2,000m

Armament: q 30mm cannons