OpenRaiser/Intern-Atlas huggingface dataset:
On Artificial-Noise Aided Transmit Design for Multi-User MISO Systems with Integrated Services
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers artificial noise (AN)-aided transmit designs for multi-user MISO systems in the eyes of service integration. Specifically, we combine two sorts of services, and serve them simultaneously: one multicast message intended for all receivers and one confidential message intended for only one receiver. The confidential message is kept perfectly secure from all the unauthorized receivers. Our goal is to jointly design the optimal input covariances for the multicast message, confidential message and AN, such that the achievable secrecy rate region is maximized subject to the sum power constraint. This secrecy rate region maximization (SRRM) problem is a nonconvex vector maximization problem. To handle it, we reformulate the SRRM problem into a provably equivalent scalar optimization problem and propose a searching method to find all of its Pareto optimal points. The equivalent scalar optimization problem is identified as a secrecy rate maximization (SRM) problem with the quality of multicast service (QoMS) constraints. Further, we show that this equivalent QoMS-constrained SRM problem, albeit nonconvex, can be efficiently handled based on a two-stage optimization approach, including solving a sequence of semidefinite programs. Moreover, we also extend the SRRM problem to an imperfect channel state information (CSI) case where a worst-case robust formulation is considered. In particular, while transmit beamforming is generally a suboptimal technique to the SRRM problem, we prove that it is optimal for the confidential message transmission whether in the perfect CSI scenario or in the imperfect CSI scenario. Finally, numerical results demonstrate that the AN-aided transmit designs are effective in expanding the achievable secrecy rate regions.
Improved Lower Bounds for Online Hypercube and Rectangle Packing
Venue: arXiv cs.DS 2017
Year: 2017

Packing a given sequence of items into as few bins as possible in an online fashion is a widely studied problem. We improve lower bounds for packing boxes into bins in two or more dimensions, both for general algorithms for squares and rectangles (in two dimensions) and for an important subclass, so-called Harmonic-type algorithms for hypercubes (in two or more dimensions). Lastly, we show that two adaptions of ideas from a one-dimensional packing algorithm to square packing do not help to break the barrier of 2.
PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations
Venue: arXiv cs.MS 2017
Year: 2017

The increasing number of applications requiring the solution of large scale singular value problems have rekindled interest in iterative methods for the SVD. Some promising recent ad- vances in large scale iterative methods are still plagued by slow convergence and accuracy limitations for computing smallest singular triplets. Furthermore, their current implementations in MATLAB cannot address the required large problems. Recently, we presented a preconditioned, two-stage method to effectively and accurately compute a small number of extreme singular triplets. In this research, we present a high-performance software, PRIMME SVDS, that implements our hybrid method based on the state-of-the-art eigensolver package PRIMME for both largest and smallest singular values. PRIMME SVDS fills a gap in production level software for computing the partial SVD, especially with preconditioning. The numerical experiments demonstrate its superior performance compared to other state-of-the-art software and its good parallel performance under strong and weak scaling.
Cryptanalyzing an Image-Scrambling Encryption Algorithm of Pixel Bits
Venue: arXiv cs.CR 2017
Year: 2017

Position scrambling (permutation) is widely used in multimedia encryption schemes and some international encryption standards, such as the Data Encryption Standard and the Advanced Encryption Standard. In this article, the authors re-evaluate the security of a typical image-scrambling encryption algorithm (ISEA). Using the internal correlation remaining in the cipher image, they disclose important visual information of the corresponding plain image in a ciphertext-only attack scenario. Furthermore, they found that the real scrambling domain--the position-scrambling scope of ISEA's scrambled elements--can be used to support an efficient known or chosen-plaintext attack on it. Detailed experimental results have verified these points and demonstrate that some advanced multimedia processing techniques can facilitate the cryptanalysis of multimedia encryption algorithms.
Working Locally Thinking Globally - Part II: Stability and Algorithms for Convolutional Sparse Coding
Venue: arXiv cs.IT 2017
Year: 2017

The convolutional sparse model has recently gained increasing attention in the signal and image processing communities, and several methods have been proposed for solving the pursuit problem emerging from it -- in particular its convex relaxation, Basis Pursuit. In the first of this two-part work, we have provided a theoretical back-bone for this model, providing guarantees for the uniqueness of the sparsest solution and for the success of pursuit algorithms by introducing the notion of stripe sparsity and other related measures. Herein, we extend the analysis to a noisy regime, thereby considering signal perturbations and model deviations. We address questions of stability of the sparsest solutions and the success of pursuit algorithms, both greedy and convex. Classical definitions such as the RIP are generalized to the convolutional model, and existing notions such as the ERC are connected to our setting. On the algorithmic side, we demonstrate how to solve the global pursuit problem by using simple local processing, thus offering a first of its kind bridge between global modeling of signals and their patch-based local treatment.
A Functional Complexity Framework for the Analysis of Telecommunication Networks
Venue: arXiv cs.SI 2017
Year: 2017

The rapid evolution of network services demands new paradigms for studying and designing networks. In order to understand the underlying mechanisms that provide network functions, we propose a framework which enables the functional analysis of telecommunication networks. This framework allows us to isolate and analyse a network function as a complex system. We propose functional topologies to visualise the relationships between system entities and enable the systematic study of interactions between them. We also define a complexity metric $C_F$ (functional complexity) which quantifies the variety of structural patterns and roles of nodes in the topology. This complexity metric provides a wholly new approach to study the operation of telecommunication networks. We study the relationship between $C_F$ and different graph structures by analysing graph theory metrics in order to recognize complex organisations. $C_F$ is equal to zero for both a full mesh topology and a disconnected topology. We show that complexity is very high for a dense structure that shows high integration (shorter average path length and high average clustering coefficient). We make a connection between functional complexity, robustness and response to changes that may appear in the system configuration. We also make a connection between the implementation and the outcome of a network function which correlates the characteristics of the outcome with the complex relationships that underpin the functional structure.
Zero-Shot Visual Recognition via Bidirectional Latent Embedding
Venue: arXiv cs.CV 2017
Year: 2017

Zero-shot learning for visual recognition, e.g., object and action recognition, has recently attracted a lot of attention. However, it still remains challenging in bridging the semantic gap between visual features and their underlying semantics and transferring knowledge to semantic categories unseen during learning. Unlike most of the existing zero-shot visual recognition methods, we propose a stagewise bidirectional latent embedding framework to two subsequent learning stages for zero-shot visual recognition. In the bottom-up stage, a latent embedding space is first created by exploring the topological and labeling information underlying training data of known classes via a proper supervised subspace learning algorithm and the latent embedding of training data are used to form landmarks that guide embedding semantics underlying unseen classes into this learned latent space. In the top-down stage, semantic representations of unseen-class labels in a given label vocabulary are then embedded to the same latent space to preserve the semantic relatedness between all different classes via our proposed semi-supervised Sammon mapping with the guidance of landmarks. Thus, the resultant latent embedding space allows for predicting the label of a test instance with a simple nearest-neighbor rule. To evaluate the effectiveness of the proposed framework, we have conducted extensive experiments on four benchmark datasets in object and action recognition, i.e., AwA, CUB-200-2011, UCF101 and HMDB51. The experimental results under comparative studies demonstrate that our proposed approach yields the state-of-the-art performance under inductive and transductive settings.
Multi Channel-Kernel Canonical Correlation Analysis for Cross-View Person Re-Identification
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we introduce a method to overcome one of the main challenges of person re-identification in multi-camera networks, namely cross-view appearance changes. The proposed solution addresses the extreme variability of person appearance in different camera views by exploiting multiple feature representations. For each feature, Kernel Canonical Correlation Analysis (KCCA) with different kernels is exploited to learn several projection spaces in which the appearance correlation between samples of the same person observed from different cameras is maximized. An iterative logistic regression is finally used to select and weigh the contributions of each feature projections and perform the matching between the two views. Experimental evaluation shows that the proposed solution obtains comparable performance on VIPeR and PRID 450s datasets and improves on PRID and CUHK01 datasets with respect to the state of the art.
New approach to Bayesian high-dimensional linear regression
Venue: arXiv cs.IT 2017
Year: 2017

Consider the problem of estimating parameters $X^n \in \mathbb{R}^n $, generated by a stationary process, from $m$ response variables $Y^m = AX^n+Z^m$, under the assumption that the distribution of $X^n$ is known. This is the most general version of the Bayesian linear regression problem. The lack of computationally feasible algorithms that can employ generic prior distributions and provide a good estimate of $X^n$ has limited the set of distributions researchers use to model the data. In this paper, a new scheme called Q-MAP is proposed. The new method has the following properties: (i) It has similarities to the popular MAP estimation under the noiseless setting. (ii) In the noiseless setting, it achieves the "asymptotically optimal performance" when $X^n$ has independent and identically distributed components. (iii) It scales favorably with the dimensions of the problem and therefore is applicable to high-dimensional setups. (iv) The solution of the Q-MAP optimization can be found via a proposed iterative algorithm which is provably robust to the error (noise) in the response variables.
Hyper Normalisation and Conditioning for Discrete Probability Distributions
Venue: arXiv cs.LO 2017
Year: 2017

Normalisation in probability theory turns a subdistribution into a proper distribution. It is a partial operation, since it is undefined for the zero subdistribution. This partiality makes it hard to reason equationally about normalisation. A novel description of normalisation is given as a mathematically well-behaved total function. The output of this `hyper' normalisation operation is a distribution of distributions. It improves reasoning about normalisation. After developing the basics of this theory of (hyper) normalisation, it is put to use in a similarly new description of conditioning, producing a distribution of conditional distributions. This is used to give a clean abstract reformulation of refinement in quantitative information flow.
The quasiequational theory of relational lattices, in the pure lattice signature (embeddability into relational lattices is undecidable)
Venue: arXiv cs.LO 2017
Year: 2017

The natural join and the inner union operations combine relations of a database. Tropashko and Spight realized that these two operations are themeet and join operations in a class of lattices, known by now as the relational lattices. They proposed then lattice theory as an algebraic approach to thetheory of databases alternative to the relational algebra. Litak et al. proposed an axiomatization of relational lattices over the signature that extends thepure lattice signature with a constant and argued that the quasiequational theory of relational lattices over this extended signature is undecidable.We prove in this paper that embeddability is undecidable for relational lattices. More precisely, it is undecidable whether a finite subdirectly-irreduciblelattice can be embedded into a relational lattice. Our proof is a reduction from the coverability problem of a multimodal frame by a universal product frameand, indirectly, from the representability problem for relation algebras. As corollaries we obtain the following results: the quasiequational theoryof relational lattices over the pure lattice signature is undecidable and has no finite base; there is a quasiequation over the pure lattice signature which holds in all the finite relational lattices but fails in an infinite relational lattice.
Scratchpad Sharing in GPUs
Venue: arXiv cs.AR 2017
Year: 2017

GPGPU applications exploit on-chip scratchpad memory available in the Graphics Processing Units (GPUs) to improve performance. The amount of thread level parallelism present in the GPU is limited by the number of resident threads, which in turn depends on the availability of scratchpad memory in its streaming multiprocessor (SM). Since the scratchpad memory is allocated at thread block granularity, part of the memory may remain unutilized. In this paper, we propose architectural and compiler optimizations to improve the scratchpad utilization. Our approach, Scratchpad Sharing, addresses scratchpad under-utilization by launching additional thread blocks in each SM. These thread blocks use unutilized scratchpad and also share scratchpad with other resident blocks. To improve the performance of scratchpad sharing, we propose Owner Warp First (OWF) scheduling that schedules warps from the additional thread blocks effectively. The performance of this approach, however, is limited by the availability of the shared part of scratchpad. We propose compiler optimizations to improve the availability of shared scratchpad. We describe a scratchpad allocation scheme that helps in allocating scratchpad variables such that shared scratchpad is accessed for short duration. We introduce a new instruction, relssp, that when executed, releases the shared scratchpad. Finally, we describe an analysis for optimal placement of relssp instructions such that shared scratchpad is released as early as possible. We implemented the hardware changes using the GPGPU-Sim simulator and implemented the compiler optimizations in Ocelot framework. We evaluated the effectiveness of our approach on 19 kernels from 3 benchmarks suites: CUDA-SDK, GPGPU-Sim, and Rodinia. The kernels that underutilize scratchpad memory show an average improvement of 19% and maximum improvement of 92.17% compared to the baseline approach.
Rooted Uniform Monotone Minimum Spanning Trees
Venue: arXiv cs.CG 2017
Year: 2017

We study the construction of the minimum cost spanning geometric graph of a given rooted point set $P$ where each point of $P$ is connected to the root by a path that satisfies a given property. We focus on two properties, namely the monotonicity w.r.t. a single direction ($y$-monotonicity) and the monotonicity w.r.t. a single pair of orthogonal directions ($xy$-monotonicity). We propose algorithms that compute the rooted $y$-monotone ($xy$-monotone) minimum spanning tree of $P$ in $O(|P|\log^2 |P|)$ (resp. $O(|P|\log^3 |P|)$) time when the direction (resp. pair of orthogonal directions) of monotonicity is given, and in $O(|P|^2\log|P|)$ time when the optimum direction (resp. pair of orthogonal directions) has to be determined. We also give simple algorithms which, given a rooted connected geometric graph, decide if the root is connected to every other vertex by paths that are all monotone w.r.t. the same direction (pair of orthogonal directions).
Event-based, 6-DOF Camera Tracking from Photometric Depth Maps
Venue: arXiv cs.CV 2017
Year: 2017

Event cameras are bio-inspired vision sensors that output pixel-level brightness changes instead of standard intensity frames. These cameras do not suffer from motion blur and have a very high dynamic range, which enables them to provide reliable visual information during high-speed motions or in scenes characterized by high dynamic range. These features, along with a very low power consumption, make event cameras an ideal complement to standard cameras for VR/AR and video game applications. With these applications in mind, this paper tackles the problem of accurate, low-latency tracking of an event camera from an existing photometric depth map (i.e., intensity plus depth information) built via classic dense reconstruction pipelines. Our approach tracks the 6-DOF pose of the event camera upon the arrival of each event, thus virtually eliminating latency. We successfully evaluate the method in both indoor and outdoor scenes and show that---because of the technological advantages of the event camera---our pipeline works in scenes characterized by high-speed motion, which are still unaccessible to standard cameras.
Recurrent Highway Networks
Venue: arXiv cs.LG 2017
Year: 2017

Many sequential processing tasks require complex nonlinear transition functions from one step to the next. However, recurrent neural networks with 'deep' transition functions remain difficult to train, even when using Long Short-Term Memory (LSTM) networks. We introduce a novel theoretical analysis of recurrent networks based on Gersgorin's circle theorem that illuminates several modeling and optimization issues and improves our understanding of the LSTM cell. Based on this analysis we propose Recurrent Highway Networks, which extend the LSTM architecture to allow step-to-step transition depths larger than one. Several language modeling experiments demonstrate that the proposed architecture results in powerful and efficient models. On the Penn Treebank corpus, solely increasing the transition depth from 1 to 10 improves word-level perplexity from 90.6 to 65.4 using the same number of parameters. On the larger Wikipedia datasets for character prediction (text8 and enwik8), RHNs outperform all previous results and achieve an entropy of 1.27 bits per character.
Language-integrated provenance
Venue: arXiv cs.PL 2017
Year: 2017

Provenance, or information about the origin or derivation of data, is important for assessing the trustworthiness of data and identifying and correcting mistakes. Most prior implementations of data provenance have involved heavyweight modifications to database systems and little attention has been paid to how the provenance data can be used outside such a system. We present extensions to the Links programming language that build on its support for language-integrated query to support provenance queries by rewriting and normalizing monadic comprehensions and extending the type system to distinguish provenance metadata from normal data. The main contribution of this article is to show that the two most common forms of provenance can be implemented efficiently and used safely as a programming language feature with no changes to the database system.
Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
Venue: arXiv cs.SC 2017
Year: 2017

Given a nonsingular $n \times n$ matrix of univariate polynomials over a field $\mathbb{K}$, we give fast and deterministic algorithms to compute its determinant and its Hermite normal form. Our algorithms use $\widetilde{\mathcal{O}}(n^ω\lceil s \rceil)$ operations in $\mathbb{K}$, where $s$ is bounded from above by both the average of the degrees of the rows and that of the columns of the matrix and $ω$ is the exponent of matrix multiplication. The soft-$O$ notation indicates that logarithmic factors in the big-$O$ are omitted while the ceiling function indicates that the cost is $\widetilde{\mathcal{O}}(n^ω)$ when $s = o(1)$. Our algorithms are based on a fast and deterministic triangularization method for computing the diagonal entries of the Hermite form of a nonsingular matrix.
Neural Tree Indexers for Text Understanding
Venue: arXiv cs.CL 2017
Year: 2017

Recurrent neural networks (RNNs) process input text sequentially and model the conditional transition between word tokens. In contrast, the advantages of recursive networks include that they explicitly model the compositionality and the recursive structure of natural language. However, the current recursive architecture is limited by its dependence on syntactic tree. In this paper, we introduce a robust syntactic parsing-independent tree structured model, Neural Tree Indexers (NTI) that provides a middle ground between the sequential RNNs and the syntactic treebased recursive models. NTI constructs a full n-ary tree by processing the input text with its node function in a bottom-up fashion. Attention mechanism can then be applied to both structure and node function. We implemented and evaluated a binarytree model of NTI, showing the model achieved the state-of-the-art performance on three different NLP tasks: natural language inference, answer sentence selection, and sentence classification, outperforming state-of-the-art recurrent and recursive neural networks.
Low RF-Complexity Technologies to Enable Millimeter-Wave MIMO with Large Antenna Array for 5G Wireless Communications
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter-wave (mmWave) MIMO with large antenna array has attracted considerable interests from academic and industry communities, as it can provide larger bandwidth and higher spectrum efficiency. However, with hundreds of antennas, the number of radio frequency (RF) chains required by mmWave MIMO is also huge, leading to unaffordable hardware cost and power consumption in practice. In this paper, we investigate low RF-complexity technologies to solve this bottleneck. We first review the evolution of low RF-complexity technologies from microwave frequencies to mmWave frequencies. Then, we discuss two promising low RF-complexity technologies for mmWave MIMO systems in detail, i.e., phased array based hybrid precoding (PAHP) and lens array based hybrid precoding (LAHP), including their principles, advantages, challenges, and recent results. We compare the performance of these two technologies to draw some insights about how they can be deployed in practice. Finally, we conclude this paper and point out some future research directions in this area.