 Title
 Interactive Interference Alignment (3 comments)

 DOI
 10.1109/JSAC.2014.2330116

 Authors
 Quan Geng
, Sreeram Kannan
, Pramod Viswanath
 Published on
 Selected Areas in Communications, IEEE Journal on (Volume:32 , Issue: 9 )
 Publication Date
 2014 / 6
 Web link
 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6832433
 Abstract
 We study interference channels (IFCs) where the interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other using fullduplex radios. The interaction can come in two ways. First is through inband interaction where sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. Second is through outofband interaction where destinations talk back to the sources on an outofband channel, which is possible from whitespace channels. The flexibility afforded by the interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties,” i.e., insensitivity to the rationality or irrationality of channel parameters, small block lengths, and finite SNR operations. We show that, for several classes of IFCs, the interactive IA scheme can achieve the optimal degrees of freedom. In particular, we show a simple scheme (having a finite block length for channels having no diversity) for threeuser and fouruser IFCs with fullduplex radios to achieve the optimal degrees of freedom even after accounting for the cost of interaction. On the technical side, we show using a Gröbner basis argument that, in a general network potentially utilizing cooperation and feedback, the optimal degrees of freedom under linear schemes of a fixed block length is the same for channel coefficients with a probability of 1. Furthermore, a numerical method to estimate this value is also presented. These tools have potentially wider utility in studying other wireless networks as well.
 Tags
 interference alignment (1) , algebra geometry (1)

 Likes
1
Dislikes
0

 Title
 The Price of Privacy in Untrusted Recommendation Engines (0 comments)

 DOI
 1207.3269

 Authors
 Siddhartha Banerjee
, Nidhi Hegde
, Laurent Massoulié
 Published on
 arXiv
 Publication Date
 2012 / 7
 Web link
 http://arxiv.org/abs/1207.3269
 Abstract
 Recent increase in online privacy concerns prompts the following question:
\
can a recommendation engine be accurate if endusers do not entrust it with
\
their private data? To provide an answer, we study the problem of learning user
\
ratings for items under local or `userend' differential privacy, a powerful,
\
formal notion of data privacy.
\
We develop a systematic approach for lower bounds on the complexity of
\
learning item structure from privatized user inputs, based on mutual
\
information. Our results identify a sample complexity separation between
\
learning in the scarce information regime and the rich information regime,
\
thereby highlighting the role of the amount of ratings (information) available
\
to each user.
\
In the informationrich regime (where each user rates at least a constant
\
fraction of items), a spectral clustering approach is shown to achieve optimal
\
sample complexity. However, the informationscarce regime (where each user
\
rates only a vanishing fraction of the total item set) is found to require a
\
fundamentally different approach. We propose a new algorithm, MaxSense, and
\
show that it achieves optimal sample complexity in this setting.
\
The techniques we develop for bounding mutual information may be of broader
\
interest. To illustrate this, we show their applicability to (i) learning based
\
on 1bit sketches (in contrast to differentially private sketches), and (ii)
\
adaptive learning, where queries can be adapted based on answers to past
\
queries.
\

 Likes
0
Dislikes
0

 Title
 Mining Associated Text and Images with DualWing Harmoniums (0 comments)

 DOI
 1207.1423

 Authors
 Eric P. Xing
, Rong Yan
, Alexander G. Hauptmann
 Published on
 arXiv
 Publication Date
 2012 / 7
 Web link
 http://arxiv.org/abs/1207.1423
 Abstract
 We propose a multiwing harmonium model for mining multimedia data that
\
extends and improves on earlier models based on twolayer random fields, which
\
capture bidirectional dependencies between hidden topic aspects and observed
\
inputs. This model can be viewed as an undirected counterpart of the twolayer
\
directed models such as LDA for similar tasks, but bears significant difference
\
in inference/learning cost tradeoffs, latent topic representations, and topic
\
mixing mechanisms. In particular, our model facilitates efficient inference and
\
robust topic mixing, and potentially provides high flexibilities in modeling
\
the latent topic spaces. A contrastive divergence and a variational algorithm
\
are derived for learning. We specialized our model to a dualwing harmonium for
\
captioned images, incorporating a multivariate Poisson for wordcounts and a
\
multivariate Gaussian for color histogram. We present empirical results on the
\
applications of this model to classification, retrieval and image annotation on
\
news video collections, and we report an extensive comparison with various
\
extant models.
\

 Likes
0
Dislikes
0

 Title
 The Supermarket Game (0 comments)

 DOI
 1202.2089

 Authors
 Jiaming Xu
, Bruce Hajek
 Published on
 arXiv
 Publication Date
 2012 / 2
 Web link
 http://arxiv.org/abs/1202.2089
 Abstract
 A supermarket game is considered with $N$ FCFS queues with unit exponential
\
service rate and global Poisson arrival rate $N \\lambda$. Upon arrival each
\
customer chooses a number of queues to be sampled uniformly at random and joins
\
the least loaded sampled queue. Customers are assumed to have cost for both
\
waiting and sampling, and they want to minimize their own expected total cost.
\
We study the supermarket game in a mean field model that corresponds to the
\
limit as $N$ converges to infinity in the sense that (i) for a fixed symmetric
\
customer strategy, the joint equilibrium distribution of any fixed number of
\
queues converges as $N \\to \\infty$ to a product distribution determined by the
\
mean field model and (ii) a Nash equilibrium for the mean field model is an
\
$\\epsilon$Nash equilibrium for the finite $N$ model with $N$ sufficiently
\
large. It is shown that there always exists a Nash equilibrium for $\\lambda <1$
\
and the Nash equilibrium is unique with homogeneous waiting cost for $\\lambda^2
\
\\le 1/2$. Furthermore, we find that the action of sampling more queues by some
\
customers has a positive externality on the other customers.
\
 Tags
 game theory (1) , queueing theory (1)

 Likes
1
Dislikes
0

 Title
 On the Local Correctness of L^1 Minimization for Dictionary Learning (0 comments)

 DOI
 1101.5672

 Authors
 Quan Geng
, Huan Wang
, John Wright
 Published on
 arXiv
 Publication Date
 2011 / 1
 Web link
 http://arxiv.org/abs/1101.5672
 Abstract
 The idea that many important classes of signals can be wellrepresented by
\
linear combinations of a small set of atoms selected from a given dictionary
\
has had dramatic impact on the theory and practice of signal processing. For
\
practical problems in which an appropriate sparsifying dictionary is not known
\
ahead of time, a very popular and successful heuristic is to search for a
\
dictionary that minimizes an appropriate sparsity surrogate over a given set of
\
sample data. While this idea is appealing, the behavior of these algorithms is
\
largely a mystery; although there is a body of empirical evidence suggesting
\
they do learn very effective representations, there is little theory to
\
guarantee when they will behave correctly, or when the learned dictionary can
\
be expected to generalize. In this paper, we take a step towards such a theory.
\
We show that under mild hypotheses, the dictionary learning problem is locally
\
wellposed: the desired solution is indeed a local minimum of the $\\ell^1$
\
norm. Namely, if $\\mb A \\in \\Re^{m \\times n}$ is an incoherent (and possibly
\
overcomplete) dictionary, and the coefficients $\\mb X \\in \\Re^{n \\times p}$
\
follow a random sparse model, then with high probability $(\\mb A,\\mb X)$ is a
\
local minimum of the $\\ell^1$ norm over the manifold of factorizations $(\\mb
\
A',\\mb X')$ satisfying $\\mb A' \\mb X' = \\mb Y$, provided the number of samples
\
$p = \\Omega(n^3 k)$. For overcomplete $\\mb A$, this is the first result showing
\
that the dictionary learning problem is locally solvable. Our analysis draws on
\
tools developed for the problem of completing a lowrank matrix from a small
\
subset of its entries, which allow us to overcome a number of technical
\
obstacles; in particular, the absence of the restricted isometry property.
\
 Tags
 dictionary learning (2) , compressed sensing (2) , sparse representation (2) , machine learning (2)

 Likes
1
Dislikes
0

 Title
 Exact Recovery of SparselyUsed Dictionaries (1 comment)

 DOI
 1206.5882

 Authors
 Daniel A. Spielman
, Huan Wang
, John Wright
 Published on
 arXiv
 Publication Date
 2012 / 6
 Web link
 http://arxiv.org/abs/1206.5882
 Abstract
 We consider the problem of learning sparsely used dictionaries with an
\
arbitrary square dictionary and a random, sparse coefficient matrix. We prove
\
that $O (n \\log n)$ samples are sufficient to uniquely determine the
\
coefficient matrix. Based on this proof, we design a polynomialtime algorithm,
\
called Exact Recovery of SparselyUsed Dictionaries (ERSpUD), and prove that
\
it probably recovers the dictionary and coefficient matrix when the coefficient
\
matrix is sufficiently sparse. Simulation results show that ERSpUD reveals the
\
true dictionary as well as the coefficients with probability higher than many
\
stateoftheart algorithms.
\
 Tags
 dictionary learning (2) , compressed sensing (2) , sparse representation (2) , machine learning (2)

 Likes
0
Dislikes
0

 Title
 Information Theory of DNA Sequencing (0 comments)

 DOI
 1203.6233

 Authors
 Abolfazl Motahari
, Guy Bresler
, David Tse
 Published on
 arXiv
 Publication Date
 2012 / 3
 Web link
 http://arxiv.org/abs/1203.6233
 Abstract
 DNA sequencing is the basic workhorse of modern day biology and medicine.
\
Shotgun sequencing is the dominant technique used: many randomly located short
\
fragments called reads are extracted from the DNA sequence, and these reads are
\
assembled to reconstruct the original sequence. A basic question is: given a
\
sequencing technology and the statistics of the DNA sequence, what is the
\
minimum number of reads required for reliable reconstruction? This number
\
provides a fundamental limit to the performance of any assembly algorithm. By
\
drawing an analogy between the DNA sequencing problem and the classic
\
communication problem, we formulate this question in terms of an information
\
theoretic notion of sequencing capacity. This is the asymptotic ratio of the
\
length of the DNA sequence to the minimum number of reads required to
\
reconstruct it reliably. We compute the sequencing capacity explicitly for a
\
simple statistical model of the DNA sequence and the read process. Using this
\
framework, we also study the impact of noise in the read process on the
\
sequencing capacity.
\

 Likes
0
Dislikes
0
Added by anonymous user on 20120630

 Title
 Channel Capacity under SubNyquist Nonuniform Sampling (0 comments)

 DOI
 1204.6049

 Authors
 Yuxin Chen
, Yonina C. Eldar
, Andrea J. Goldsmith
 Published on
 arXiv
 Publication Date
 2012 / 4
 Web link
 http://arxiv.org/abs/1204.6049
 Abstract
 This paper develops the capacity of sampled analog channels under a
\
subNyquist sampling rate constraint. We consider a general class of
\
timepreserving sampling methods which includes irregular nonuniform sampling.
\
Our results indicate that the optimal sampling structures extract out a set of
\
frequencies that exhibits the highest SNR among all spectral sets of measure
\
equal to the sampling rate. The sampled capacity can be attained through
\
filterbank sampling with uniform sampling at each branch with possibly
\
different rates, or through a single branch of modulation and filtering
\
followed by uniform sampling, and the sampled capacity is monotonically
\
nondecreasing with the sampling rate. These results indicate that the optimal
\
sampling schemes suppress aliasing, and that employing irregular nonuniform
\
sampling does not provide capacity gain over uniform sampling sets with
\
appropriate preprocessing for a large class of channels.
\

 Likes
0
Dislikes
0
Added by anonymous user on 20120629

 Title
 Bargaining dynamics in exchange networks (1 comment)

 DOI
 1004.2079

 Authors
 Mohsen Bayati
, Christian Borgs
, Jennifer Chayes
, Yashodhan Kanoria
, Andrea Montanari
 Published on
 47 pages, SODA 2011, invited to Journal of Economic Theory
 Publication Date
 2011 / 12
 Web link
 http://arxiv.org/abs/1004.2079
 Abstract
 We consider a onesided assignment market or exchange network with transferable utility and propose a model for the dynamics of bargaining in such a market. Our dynamical model is local, involving iterative updates of 'offers' based on estimated best alternative matches, in the spirit of pairwise Nash bargaining. We establish that when a balanced outcome (a generalization of the pairwise Nash bargaining solution to networks) exists, our dynamics converges rapidly to such an outcome. We extend our results to the cases of (i) general agent 'capacity constraints', i.e., an agent may be allowed to participate in multiple matches, and (ii) 'unequal bargaining powers' (where we also find a surprising change in rate of convergence).

 Likes
0
Dislikes
0

 Title
 Multicommodity Flows and Cuts in Polymatroidal Networks (2 comments)

 DOI
 1110.6832

 Authors
 Chandra Chekuri
, Sreeram Kannan
, Adnan Raja
, Pramod Viswanath
 Published on
 ITCS
 Publication Date
 2012 / 1
 Web link
 http://arxiv.org/abs/1110.6832
 Abstract
 We consider multicommodity flow and cut problems in {\\em polymatroidal} networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel and Hassin in the singlecommodity setting and are closely related to the submodular flow model of Edmonds and Giles; the wellknown maxflowmincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far as the authors are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks.

 Likes
0
Dislikes
0
