OpenRaiser/Intern-Atlas huggingface dataset:
Multiuser MIMO Sequential Beamforming with Full-duplex Training
Venue: arXiv cs.IT 2017
Year: 2017

Multiple transmitting antennas can considerably increase the downlink spectral efficiency by beamforming to multiple users at the same time. However, multiuser beamforming requires channel state information (CSI) at the transmitter, which leads to training overhead and reduces overall achievable spectral efficiency. In this paper, we propose and analyze a sequential beamforming strategy that utilizes full-duplex base station to implement downlink data transmission concurrently with CSI acquisition via in-band closed or open loop training. Our results demonstrate that full-duplex capability can improve the spectral efficiency of uni-directional traffic, by leveraging it to reduce the control overhead of CSI estimation. In moderate SNR regimes, we analytically derive tight approximations for the optimal training duration and characterize the associated respective spectral efficiency. We further characterize the enhanced multiplexing gain performance in the high SNR regime. In both regimes, the performance of the proposed full-duplex strategy is compared to the half-duplex counterpart to quantify spectral efficiency improvement. With experimental data [1] and 3D channel model [2] from 3GPP, in a 1.4 MHz 8X8 system LTE system with the block length of 500 symbols, the proposed strategy attains a spectral efficiency improvement of 130% and 8% with closed and open loop training, respectively.
On the Capacity of Block Multiantenna Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we consider point-to-point multiantenna channels with certain block distributional symmetries which do not require the entries of the channel matrix to be either Gaussian, or independent, or identically distributed. A main contribution is a capacity theorem for these channels, which might be regarded as a generalization of Telatar's theorem (1999), which reduces the numerical optimization domain in the capacity computation. With this information theoretic result and some free probability arguments, we prove an asymptotic capacity theorem that, in addition to reducing the optimization domain, does not depend on the dimension of the channel matrix. This theorem allows us to apply free probability techniques to numerically compute the asymptotic capacity of the channels under consideration. These theorems provide a very efficient method for numerically approximating both the capacity and a capacity achieving input covariance matrix of certain channels.
Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination
Venue: arXiv cs.GT 2017
Year: 2017

We study a basic auction design problem with online supply. There are two unit-demand bidders and two types of items. The first item type will arrive first for sure, and the second item type may or may not arrive. The auctioneer has to decide the allocation of an item immediately after each item arrives, but is allowed to compute payments after knowing how many items arrived. For this problem we show that there is no deterministic truthful and individually rational mechanism that, even with unbounded computational resources, gets any finite approximation factor to the optimal social welfare.
Secure Numerical and Logical Multi Party Operations
Venue: arXiv cs.CR 2017
Year: 2017

We derive algorithms for efficient secure numerical and logical operations using a recently introduced scheme for secure multi-party computation~\cite{sch15} in the semi-honest model ensuring statistical or perfect security. To derive our algorithms for trigonometric functions, we use basic mathematical laws in combination with properties of the additive encryption scheme in a novel way. For division and logarithm we use a new approach to compute a Taylor series at a fixed point for all numbers. All our logical operations such as comparisons and large fan-in AND gates are perfectly secure. Our empirical evaluation yields speed-ups of more than a factor of 100 for the evaluated operations compared to the state-of-the-art.
The capacity of Bernoulli nonadaptive group testing
Venue: arXiv cs.IT 2017
Year: 2017

We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a converse on the COMP algorithm of Chan et al, and a bound on the SSS algorithm similar to that given by Aldridge, Baldassini, and Johnson. Our result has a number of important corollaries, in particular that, in denser cases, Bernoulli nonadaptive group testing is strictly worse than the best adaptive strategies.
Gated Graph Sequence Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Graph-structured data appears frequently in domains including chemistry, natural language semantics, social networks, and knowledge bases. In this work, we study feature learning techniques for graph-structured inputs. Our starting point is previous work on Graph Neural Networks (Scarselli et al., 2009), which we modify to use gated recurrent units and modern optimization techniques and then extend to output sequences. The result is a flexible and broadly useful class of neural network models that has favorable inductive biases relative to purely sequence-based models (e.g., LSTMs) when the problem is graph-structured. We demonstrate the capabilities on some simple AI (bAbI) and graph algorithm learning tasks. We then show it achieves state-of-the-art performance on a problem from program verification, in which subgraphs need to be matched to abstract data structures.
EigenRec: Generalizing PureSVD for Effective and Efficient Top-N Recommendations
Venue: arXiv cs.IR 2017
Year: 2017

We introduce EigenRec; a versatile and efficient Latent-Factor framework for Top-N Recommendations that includes the well-known PureSVD algorithm as a special case. EigenRec builds a low dimensional model of an inter-item proximity matrix that combines a similarity component, with a scaling operator, designed to control the influence of the prior item popularity on the final model. Seeing PureSVD within our framework provides intuition about its inner workings, exposes its inherent limitations, and also, paves the path towards painlessly improving its recommendation performance. A comprehensive set of experiments on the MovieLens and the Yahoo datasets based on widely applied performance metrics, indicate that EigenRec outperforms several state-of-the-art algorithms, in terms of Standard and Long-Tail recommendation accuracy, exhibiting low susceptibility to sparsity, even in its most extreme manifestations -- the Cold-Start problems. At the same time EigenRec has an attractive computational profile and it can apply readily in large-scale recommendation settings.
FRIST - Flipping and Rotation Invariant Sparsifying Transform Learning and Applications
Venue: arXiv cs.LG 2017
Year: 2017

Features based on sparse representation, especially using the synthesis dictionary model, have been heavily exploited in signal processing and computer vision. However, synthesis dictionary learning typically involves NP-hard sparse coding and expensive learning steps. Recently, sparsifying transform learning received interest for its cheap computation and its optimal updates in the alternating algorithms. In this work, we develop a methodology for learning Flipping and Rotation Invariant Sparsifying Transforms, dubbed FRIST, to better represent natural images that contain textures with various geometrical directions. The proposed alternating FRIST learning algorithm involves efficient optimal updates. We provide a convergence guarantee, and demonstrate the empirical convergence behavior of the proposed FRIST learning approach. Preliminary experiments show the promising performance of FRIST learning for sparse image representation, segmentation, denoising, robust inpainting, and compressed sensing-based magnetic resonance image reconstruction.
Universal halting times in optimization and machine learning
Venue: arXiv cs.LG 2017
Year: 2017

The authors present empirical distributions for the halting time (measured by the number of iterations to reach a given accuracy) of optimization algorithms applied to two random systems: spin glasses and deep learning. Given an algorithm, which we take to be both the optimization routine and the form of the random landscape, the fluctuations of the halting time follow a distribution that, after centering and scaling, remains unchanged even when the distribution on the landscape is changed. We observe two qualitative classes: A Gumbel-like distribution that appears in Google searches, human decision times, the QR eigenvalue algorithm and spin glasses, and a Gaussian-like distribution that appears in conjugate gradient method, deep network with MNIST input data and deep network with random input data. This empirical evidence suggests presence of a class of distributions for which the halting time is independent of the underlying distribution under some conditions.
Semantic Segmentation of Colon Glands with Deep Convolutional Neural Networks and Total Variation Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Segmentation of histopathology sections is an ubiquitous requirement in digital pathology and due to the large variability of biological tissue, machine learning techniques have shown superior performance over standard image processing methods. As part of the GlaS@MICCAI2015 colon gland segmentation challenge, we present a learning-based algorithm to segment glands in tissue of benign and malignant colorectal cancer. Images are preprocessed according to the Hematoxylin-Eosin staining protocol and two deep convolutional neural networks (CNN) are trained as pixel classifiers. The CNN predictions are then regularized using a figure-ground segmentation based on weighted total variation to produce the final segmentation result. On two test sets, our approach achieves a tissue classification accuracy of 98% and 94%, making use of the inherent capability of our system to distinguish between benign and malignant tissue.
End-to-end Learning of Action Detection from Frame Glimpses in Videos
Venue: arXiv cs.CV 2017
Year: 2017

In this work we introduce a fully end-to-end approach for action detection in videos that learns to directly predict the temporal bounds of actions. Our intuition is that the process of detecting actions is naturally one of observation and refinement: observing moments in video, and refining hypotheses about when an action is occurring. Based on this insight, we formulate our model as a recurrent neural network-based agent that interacts with a video over time. The agent observes video frames and decides both where to look next and when to emit a prediction. Since backpropagation is not adequate in this non-differentiable setting, we use REINFORCE to learn the agent's decision policy. Our model achieves state-of-the-art results on the THUMOS'14 and ActivityNet datasets while observing only a fraction (2% or less) of the video frames.
Constant Factor Approximation for ATSP with Two Edge Weights
Venue: arXiv cs.DS 2017
Year: 2017

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest.
Adapting Deep Visuomotor Representations with Weak Pairwise Constraints
Venue: arXiv cs.CV 2017
Year: 2017

Real-world robotics problems often occur in domains that differ significantly from the robot's prior training environment. For many robotic control tasks, real world experience is expensive to obtain, but data is easy to collect in either an instrumented environment or in simulation. We propose a novel domain adaptation approach for robot perception that adapts visual representations learned on a large easy-to-obtain source dataset (e.g. synthetic images) to a target real-world domain, without requiring expensive manual data annotation of real world data before policy search. Supervised domain adaptation methods minimize cross-domain differences using pairs of aligned images that contain the same object or scene in both the source and target domains, thus learning a domain-invariant representation. However, they require manual alignment of such image pairs. Fully unsupervised adaptation methods rely on minimizing the discrepancy between the feature distributions across domains. We propose a novel, more powerful combination of both distribution and pairwise image alignment, and remove the requirement for expensive annotation by using weakly aligned pairs of images in the source and target domains. Focusing on adapting from simulation to real world data using a PR2 robot, we evaluate our approach on a manipulation task and show that by using weakly paired images, our method compensates for domain shift more effectively than previous techniques, enabling better robot performance in the real world.
Innovation Pursuit: A New Approach to Subspace Clustering
Venue: arXiv cs.CV 2017
Year: 2017

In subspace clustering, a group of data points belonging to a union of subspaces are assigned membership to their respective subspaces. This paper presents a new approach dubbed Innovation Pursuit (iPursuit) to the problem of subspace clustering using a new geometrical idea whereby subspaces are identified based on their relative novelties. We present two frameworks in which the idea of innovation pursuit is used to distinguish the subspaces. Underlying the first framework is an iterative method that finds the subspaces consecutively by solving a series of simple linear optimization problems, each searching for a direction of innovation in the span of the data potentially orthogonal to all subspaces except for the one to be identified in one step of the algorithm. A detailed mathematical analysis is provided establishing sufficient conditions for iPursuit to correctly cluster the data. The proposed approach can provably yield exact clustering even when the subspaces have significant intersections. It is shown that the complexity of the iterative approach scales only linearly in the number of data points and subspaces, and quadratically in the dimension of the subspaces. The second framework integrates iPursuit with spectral clustering to yield a new variant of spectral-clustering-based algorithms. The numerical simulations with both real and synthetic data demonstrate that iPursuit can often outperform the state-of-the-art subspace clustering algorithms, more so for subspaces with significant intersections, and that it significantly improves the state-of-the-art result for subspace-segmentation-based face clustering.
Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function) and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work (2015). In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú (2012). The converse part uses a perturbation argument by Gu and Effros (2009) in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: (i) a generalization of various type covering lemmas; and (ii) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities.
Proactive Eavesdropping via Cognitive Jamming in Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

To enhance the national security, there is a growing need for government agencies to legitimately monitor suspicious communication links for preventing intended crimes and terror attacks. In this paper, we propose a new wireless information surveillance paradigm by investigating a scenario where a legitimate monitor aims to intercept a suspicious wireless communication link over fading channels. The legitimate monitor can successfully eavesdrop (decode) the information of the suspicious link at each fading state only when its achievable data rate is no smaller than that at the suspicious receiver. In practice, such legitimate eavesdropping is particularly challenging, since the legitimate monitor may be far away from the suspicious transmitter and cannot eavesdrop efficiently. To overcome this issue, we propose a new approach, namely proactive eavesdropping via cognitive jamming, in which the legitimate monitor purposely jams the receiver so as to change the suspicious communication (e.g., to a smaller data rate) for overhearing more efficiently. In particular, we consider delay-sensitive and delay-tolerant applications for the suspicious data communications, under which the legitimate monitor maximizes the eavesdropping non-outage probability for event-based monitoring and the relative eavesdropping rate for content analysis, respectively, by optimizing its jamming power allocation over different fading states subject to an average power constraint. Numerical results show that the proposed proactive eavesdropping via cognitive jamming approach greatly outperforms the conventional passive eavesdropping without jamming and the proactive eavesdropping with constant-power jamming.
From One Point to A Manifold: Knowledge Graph Embedding For Precise Link Prediction
Venue: arXiv cs.AI 2017
Year: 2017

Knowledge graph embedding aims at offering a numerical knowledge representation paradigm by transforming the entities and relations into continuous vector space. However, existing methods could not characterize the knowledge graph in a fine degree to make a precise prediction. There are two reasons: being an ill-posed algebraic system and applying an overstrict geometric form. As precise prediction is critical, we propose an manifold-based embedding principle (\textbf{ManifoldE}) which could be treated as a well-posed algebraic system that expands the position of golden triples from one point in current models to a manifold in ours. Extensive experiments show that the proposed models achieve substantial improvements against the state-of-the-art baselines especially for the precise prediction task, and yet maintain high efficiency.
A Mathematical Theory of Deep Convolutional Neural Networks for Feature Extraction
Venue: arXiv cs.IT 2017
Year: 2017

Deep convolutional neural networks have led to breakthrough results in numerous practical machine learning tasks such as classification of images in the ImageNet data set, control-policy-learning to play Atari games or the board game Go, and image captioning. Many of these applications first perform feature extraction and then feed the results thereof into a trainable classifier. The mathematical analysis of deep convolutional neural networks for feature extraction was initiated by Mallat, 2012. Specifically, Mallat considered so-called scattering networks based on a wavelet transform followed by the modulus non-linearity in each network layer, and proved translation invariance (asymptotically in the wavelet scale parameter) and deformation stability of the corresponding feature extractor. This paper complements Mallat's results by developing a theory that encompasses general convolutional transforms, or in more technical parlance, general semi-discrete frames (including Weyl-Heisenberg filters, curvelets, shearlets, ridgelets, wavelets, and learned filters), general Lipschitz-continuous non-linearities (e.g., rectified linear units, shifted logistic sigmoids, hyperbolic tangents, and modulus functions), and general Lipschitz-continuous pooling operators emulating, e.g., sub-sampling and averaging. In addition, all of these elements can be different in different network layers. For the resulting feature extractor we prove a translation invariance result of vertical nature in the sense of the features becoming progressively more translation-invariant with increasing network depth, and we establish deformation sensitivity bounds that apply to signal classes such as, e.g., band-limited functions, cartoon functions, and Lipschitz functions.
Linear lambda terms as invariants of rooted trivalent maps
Venue: arXiv cs.LO 2017
Year: 2017

The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between $α$-equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the "easy" direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.