Welcome to ShareRI: Share Research Ideas

 

ShareRI is a website where people can freely express their opinions on published research papers, and share their insights on interesting research problems. ShareRI is also a wonderful platform for researchers to present their work and help them get feedback from the readers.

 

The mission of ShareRI is to make research more interactive and fun!      Video Demo      More Info     

 

Sign Up Login

Most popular tags:



Recently added Papers (More)


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 full-duplex radios. The interaction can come in two ways. First is through in-band interaction where sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. Second is through out-of-band interaction where destinations talk back to the sources on an out-of-band channel, which is possible from white-space 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 three-user and four-user IFCs with full-duplex 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
Added by Quan Geng on 2015-08-01
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 end-users 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 `user-end' 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 information-rich 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 information-scarce 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 1-bit 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
Added by Quan Geng on 2012-07-16
Title
Mining Associated Text and Images with Dual-Wing 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 multi-wing harmonium model for mining multimedia data that \ extends and improves on earlier models based on two-layer random fields, which \ capture bidirectional dependencies between hidden topic aspects and observed \ inputs. This model can be viewed as an undirected counterpart of the two-layer \ 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 dual-wing harmonium for \ captioned images, incorporating a multivariate Poisson for word-counts 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
Added by Tim Weninger on 2012-07-09
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
Added by Quan Geng on 2012-07-05
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 well-represented 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 \ well-posed: 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 low-rank 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
Added by Quan Geng on 2012-07-02
Title
Exact Recovery of Sparsely-Used 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 polynomial-time algorithm, \ called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that \ it probably recovers the dictionary and coefficient matrix when the coefficient \ matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the \ true dictionary as well as the coefficients with probability higher than many \ state-of-the-art algorithms. \
Tags
dictionary learning (2) , compressed sensing (2) , sparse representation (2) , machine learning (2)
 
Likes 0      Dislikes 0
Added by Quan Geng on 2012-07-01
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 2012-06-30
Title
Channel Capacity under Sub-Nyquist 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 \ sub-Nyquist sampling rate constraint. We consider a general class of \ time-preserving 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 \ filter-bank 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 \ non-decreasing 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 2012-06-29
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 one-sided 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
Added by Quan Geng on 2012-06-26
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 single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles; the well-known maxflow-mincut 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
Added by Sreeram on 2012-06-26