# 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

## Most popular tags:

 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 Grö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)   1      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. \   0      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. \   0      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)   1      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)   1      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)   0      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. \   0      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. \   0      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).   0      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.   0      0 Added by Sreeram on 2012-06-26