Poster Session and Reception
Tuesday, February 14, 2012 - 4:15pm - 5:30pm
- Poster - Approximation for Nonunique Probe Selection
Ding-Zhu Du (University of Texas)
Given a binary matrix $M$, find submatrix with the same number of columns and minimum
number of raws such that all boolean sums of at most $d$ columns are distinct. We show
that for any fixed $d$, this problem has no polynomial-time $o(\log n)$-approximation
unless NP-P. Meanwhile, some approximation algorithms are also presented.
- Poster - Finding one of m defective elements
Christian Deppe (Universität Bielefeld)
In contrast to the classical goal of group testing we want to find onw defective elements of $D$
defective elements. We examine four
different test functions. We give adaptive strategies and lower bounds for the number of tests.
We treat the cases if the number of defectives are known and if the number of defectives are bounded.
- Poster - Upgraded Separate Testing of Inputs in Compressive Sensing
Mikhail Malyutov (Northeastern University)
Screening experiments (SE) deal with finding a small number s Active
Inputs (AIs) out of a vast total amount t of inputs in a regressionmodel.
Of special interest in the SE theory is finding the so-called maximal rate
For a set of t elements, denote the set of its s-subsets by (s, t). Introduce
a noisy system with t binary inputs and one output y. Suppose
that only s themby a sequence of N trials resulting in outputs yN. Suppose a ‘(f,
separating’ (N × t) matrix exists for N Nf (s, t,
) such that it allows
identifying the true s-subset of uniformly distributed AIs with probability
under analysis f : yN ! (s, t) of outputs. Nf (s, t,
admits equivalent definition in terms of random design matrices which
turn out to be asymptotically optimal under
> 0. The f-capacity
Cf (s) = limt!1(log t/Nf (s, t,
)) for any
> 0 is the ‘limit for the per-
formance of the f-analysis’.
We obtained tight capacity bounds ,  by formalizing CSS as a special
case of Multi-Access Communication Channels (MAC) of information
transmission capacity region construction developed by R. Ahlswede
in  and comparing CSS’ maximal rate (capacity) with small error for
two practical methods of outputs’ analysis under the optimal CSS design
motivated by applications like  . Recovering Active Inputs with
small error probability and accurate parameter estimation are both possible
with rates less than capacity and impossible with larger rates.
A staggering amount of attention was recently devoted to the study
of compressive sensing and related areas using sparse priors in over
parameterized linear models which may be viewed as a special case of
our models with continuous input levels.
The threshold phenomenon was empirically observed in early papers
,  : as the dimension of a randominstance of a problem grows there
is a sharp transition from successful recovery to failure as a function
of the number of observations versus the dimension and sparsity of the
unknown signal. Finding this threshold is closely related to our capacity
evaluation. Some threshold bounds for the compressive sensing were
made using standard information-theoretic tools, e.g. in 
- Poster - Hierarchical topological network analysis of anatomical human brain connectivity and differences related to sex and kinship.
Julio Duarte (University of Minnesota, Twin Cities)
Modern non-invasive brain imaging technologies, such as diffusion weighted magnetic resonance imaging
(DWI), enable the mapping of neural fiber tracts in the white matter, providing a basis to reconstruct a detailed
map of brain structural connectivity networks. Brain connectivity networks differ from random networks
in their topology, which can be measured using small worldness, modularity, and high-degree
nodes (hubs). Still, little is known about how individual differences in structural brain network properties relate
to age, sex, or genetic differences. Recently, some groups have reported brain network biomarkers that
enable differentiation among individuals, pairs of individuals, and groups of individuals. In addition to studying
new topological features, here we provide a unifying general method to investigate topological brain networks
and connectivity differences between individuals, pairs of individuals, and groups of individuals at
several levels of the data hierarchy, while appropriately controlling false discovery rate (FDR) errors. We
apply our new method to a large dataset of high quality brain connectivity networks obtained from High Angular
Resolution Diffusion Imaging (HARDI) tractography in 303 young adult twins, siblings, and unrelated
people. Our proposed approach can accurately classify brain connectivity networks based on sex (93% accuracy)
and kinship (88.5% accuracy). We find statistically significant differences associated with sex and kinship
both in the brain connectivity networks and in derived topological metrics, such as the clustering
coefficient and the communicability matrix.