OpenRaiser/Intern-Atlas huggingface dataset:
Non-Orthogonal Multiple Access For Cooperative Communications: Challenges, Opportunities, And Trends
Venue: arXiv cs.IT 2018
Year: 2018

Non-orthogonal multiple access (NOMA) is a promising radio access technique for next-generation wireless networks. In this article, we investigate the NOMA-based cooperative relay network. We begin with an introduction of the existing relay-assisted NOMA systems by classifying them into three categories: uplink, downlink, and composite architectures. Then, we discuss their principles and key features, and provide a comprehensive comparison from the perspective of spectral efficiency, energy efficiency, and total transmit power. A novel strategy termed hybrid power allocation is further discussed for the composite architecture, which can reduce the computational complexity and signaling overhead at the expense of marginal sum rate degradation. Finally, major challenges, opportunities, and future research trends for the design of NOMA-based cooperative relay systems with other techniques are also highlighted to provide insights for researchers in this field.
Enlarging Context with Low Cost: Efficient Arithmetic Coding with Trimmed Convolution
Venue: arXiv cs.CV 2018
Year: 2018

Arithmetic coding is an essential class of coding techniques. One key issue of arithmetic encoding method is to predict the probability of the current coding symbol from its context, i.e., the preceding encoded symbols, which usually can be executed by building a look-up table (LUT). However, the complexity of LUT increases exponentially with the length of context. Thus, such solutions are limited to modeling large context, which inevitably restricts the compression performance. Several recent deep neural network-based solutions have been developed to account for large context, but are still costly in computation. The inefficiency of the existing methods are mainly attributed to that probability prediction is performed independently for the neighboring symbols, which actually can be efficiently conducted by shared computation. To this end, we propose a trimmed convolutional network for arithmetic encoding (TCAE) to model large context while maintaining computational efficiency. As for trimmed convolution, the convolutional kernels are specially trimmed to respect the compression order and context dependency of the input symbols. Benefited from trimmed convolution, the probability prediction of all symbols can be efficiently performed in one single forward pass via a fully convolutional network. Furthermore, to speed up the decoding process, a slope TCAE model is presented to divide the codes from a 3D code map into several blocks and remove the dependency between the codes inner one block for parallel decoding, which can 60x speed up the decoding process. Experiments show that our TCAE and slope TCAE attain better compression ratio in lossless gray image compression, and can be adopted in CNN-based lossy image compression to achieve state-of-the-art rate-distortion performance with real-time encoding speed.
Searching for Maximum Out-Degree Vertices in Tournaments
Venue: arXiv cs.DS 2018
Year: 2018

A vertex $x$ in a tournament $T$ is called a king if for every vertex $y$ of $T$ there is a directed path from $x$ to $y$ of length at most 2. It is not hard to show that every vertex of maximum out-degree in a tournament is a king. However, tournaments may have kings which are not vertices of maximum out-degree. A binary inquiry asks for the orientation of the edge between a pair of vertices and receives the answer. The cost of finding a king in an unknown tournament is the number of binary inquiries required to detect a king. For the cost of finding a king in a tournament, in the worst case, Shen, Sheng and Wu (SIAM J. Comput., 2003) proved a lower and upper bounds of $Ω(n^{4/3})$ and $O(n^{3/2})$, respectively. In contrast to their result, we prove that the cost of finding a vertex of maximum out-degree is ${n \choose 2} -O(n)$ in the worst case.
Full Wafer Redistribution and Wafer Embedding as Key Technologies for a Multi-Scale Neuromorphic Hardware Cluster
Venue: arXiv cs.ET 2018
Year: 2018

Together with the Kirchhoff-Institute for Physics(KIP) the Fraunhofer IZM has developed a full wafer redistribution and embedding technology as base for a large-scale neuromorphic hardware system. The paper will give an overview of the neuromorphic computing platform at the KIP and the associated hardware requirements which drove the described technological developments. In the first phase of the project standard redistribution technologies from wafer level packaging were adapted to enable a high density reticle-to-reticle routing on 200mm CMOS wafers. Neighboring reticles were interconnected across the scribe lines with an 8μm pitch routing based on semi-additive copper metallization. Passivation by photo sensitive benzocyclobutene was used to enable a second intra-reticle routing layer. Final IO pads with flash gold were generated on top of each reticle. With that concept neuromorphic systems based on full wafers could be assembled and tested. The fabricated high density inter-reticle routing revealed a very high yield of larger than 99.9%. In order to allow an upscaling of the system size to a large number of wafers with feasible effort a full wafer embedding concept for printed circuit boards was developed and proven in the second phase of the project. The wafers were thinned to 250μm and laminated with additional prepreg layers and copper foils into a core material. After lamination of the PCB panel the reticle IOs of the embedded wafer were accessed by micro via drilling, copper electroplating, lithography and subtractive etching of the PCB wiring structure. The created wiring with 50um line width enabled an access of the reticle IOs on the embedded wafer as well as a board level routing. The panels with the embedded wafers were subsequently stressed with up to 1000 thermal cycles between 0C and 100C and have shown no severe failure formation over the cycle time.
A Tight Converse to the Spectral Resolution Limit via Convex Programming
Venue: arXiv cs.IT 2018
Year: 2018

It is now well understood that convex programming can be used to estimate the frequency components of a spectrally sparse signal from $2m+1$ uniform temporal measurements. It is conjectured that a phase transition on the success of the total-variation regularization occurs when the distance between the spectral components of the signal to estimate crosses $1/m$. We prove the necessity part of this conjecture by demonstrating that this regularization can fail whenever the spectral distance of the signal of interest is asymptotically equal to $1/m$.
Predicting Movie Genres Based on Plot Summaries
Venue: arXiv cs.CL 2018
Year: 2018

This project explores several Machine Learning methods to predict movie genres based on plot summaries. Naive Bayes, Word2Vec+XGBoost and Recurrent Neural Networks are used for text classification, while K-binary transformation, rank method and probabilistic classification with learned probability threshold are employed for the multi-label problem involved in the genre tagging task.Experiments with more than 250,000 movies show that employing the Gated Recurrent Units (GRU) neural networks for the probabilistic classification with learned probability threshold approach achieves the best result on the test set. The model attains a Jaccard Index of 50.0%, a F-score of 0.56, and a hit rate of 80.5%.
Localizability-Constrained Deployment of Mobile Robotic Networks with Noisy Range Measurements
Venue: arXiv cs.SY 2018
Year: 2018

When nodes in a mobile network use relative noisy measurements with respect to their neighbors to estimate their positions, the overall connectivity and geometry of the measurement network has a critical influence on the achievable localization accuracy. This paper considers the problem of deploying a mobile robotic network implementing a cooperative localization scheme based on range measurements only, while attempting to maintain a network geometry that is favorable to estimating the robots' positions with high accuracy. The quality of the network geometry is measured by a "localizability" function serving as potential field for robot motion planning. This function is built from the Cramér-Rao bound, which provides for a given geometry a lower bound on the covariance matrix achievable by any unbiased position estimator that the robots might implement using their relative measurements. We describe gradient descent-based motion planners for the robots that attempt to optimize or constrain different variations of the network's localizability function, and discuss ways of implementing these controllers in a distributed manner. Finally, the paper also establishes formal connections between our statistical point of view and maintaining a form of weighted rigidity for the graph capturing the relative range measurements.
Improving Communication Patterns in Polyhedral Process Networks
Venue: arXiv cs.DC 2018
Year: 2018

Embedded system performances are bounded by power consumption. The trend is to offload greedy computations on hardware accelerators as GPU, Xeon Phi or FPGA. FPGA chips combine both flexibility of programmable chips and energy-efficiency of specialized hardware and appear as a natural solution. Hardware compilers from high-level languages (High-level synthesis, HLS) are required to exploit all the capabilities of FPGA while satisfying tight time-to-market constraints. Compiler optimizations for parallelism and data locality restructure deeply the execution order of the processes, hence the read/write patterns in communication channels. This breaks most FIFO channels, which have to be implemented with addressable buffers. Expensive hardware is required to enforce synchronizations, which often results in dramatic performance loss. In this paper, we present an algorithm to partition the communications so that most FIFO channels can be recovered after a loop tiling, a key optimization for parallelism and data locality. Experimental results show a drastic improvement of FIFO detection for regular kernels at the cost of a few additional storage. As a bonus, the storage can even be reduced in some cases.
Sending Information Through Status Updates
Venue: arXiv cs.IT 2018
Year: 2018

We consider an energy harvesting transmitter sending status updates regarding a physical phenomenon it observes to a receiver. Different from the existing literature, we consider a scenario where the status updates carry information about an independent message. The transmitter encodes this message into the timings of the status updates. The receiver needs to extract this encoded information, as well as update the status of the observed phenomenon. The timings of the status updates, therefore, determine both the age of information (AoI) and the message rate (rate). We study the tradeoff between the achievable message rate and the achievable average AoI. We propose several achievable schemes and compare their rate-AoI performances.
Comparing the power of advice strings: a notion of complexity for infinite words
Venue: arXiv cs.FL 2018
Year: 2018

This paper is the extended version of On the Complexity of Infinite Advice Strings (ICALP 2018). We investigate a notion of comparison between infinite strings. In a general way, if M is a computation model (e.g. Turing machines) and C a class of objects (e.g. languages), the complexity of an infinite word alpha can be measured with respect to the amount of objects from C that are presentable with machines from M using alpha as an oracle. In our case, the model M is finite automata and the objects C are either recognized languages or presentable structures, known respectively as advice regular languages and advice automatic structures. This leads to several different classifications of infinite words that are studied in detail; we also derive logical and computational equivalent measures. Our main results explore the connections between classes of advice automatic structures, MSO-transductions and two-way transducers. They suggest a closer study of the resulting hierarchy over infinite words.
On the Complexity of the Weighted Fused Lasso
Venue: arXiv cs.LG 2018
Year: 2018

The solution path of the 1D fused lasso for an $n$-dimensional input is piecewise linear with $\mathcal{O}(n)$ segments (Hoefling et al. 2010 and Tibshirani et al 2011). However, existing proofs of this bound do not hold for the weighted fused lasso. At the same time, results for the generalized lasso, of which the weighted fused lasso is a special case, allow $Ω(3^n)$ segments (Mairal et al. 2012). In this paper, we prove that the number of segments in the solution path of the weighted fused lasso is $\mathcal{O}(n^2)$, and that, for some instances, it is $Ω(n^2)$. We also give a new, very simple, proof of the $\mathcal{O}(n)$ bound for the fused lasso.
Vehicle Routing with Subtours
Venue: arXiv cs.DS 2018
Year: 2018

When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items are initially loaded in one vehicle and should be distributed before a given deadline Δ. In addition to travel time and time for deliveries, we assume that there is a fixed delay for handing over an item from one vehicle to another. We will show that it is easy to decide whether an instance is feasible, i.e., whether it is possible to deliver all items before the deadline Δ. We then consider computing a feasible tour of minimum cost, where we incur a cost per unit distance traveled by the vehicles, and a setup cost for every used vehicle. Our problem arises in practical applications and generalizes classical problems such as shallow-light trees and the bounded-latency problem. Our main result is a polynomial-time algorithm that, for any given ε > 0 and any feasible instance, computes a solution that delivers all items before time (1+ ε)Δ and has cost O(1 + 1 / ε) OPT, where OPT is the minimum cost of any feasible solution. We show that our result is best possible in the sense that any improvement would lead to progress on 25-year-old questions on shallow-light trees.
Detecting abnormal events in video using Narrowed Normality Clusters
Venue: arXiv cs.CV 2018
Year: 2018

We formulate the abnormal event detection problem as an outlier detection task and we propose a two-stage algorithm based on k-means clustering and one-class Support Vector Machines (SVM) to eliminate outliers. In the feature extraction stage, we propose to augment spatio-temporal cubes with deep appearance features extracted from the last convolutional layer of a pre-trained neural network. After extracting motion and appearance features from the training video containing only normal events, we apply k-means clustering to find clusters representing different types of normal motion and appearance features. In the first stage, we consider that clusters with fewer samples (with respect to a given threshold) contain mostly outliers, and we eliminate these clusters altogether. In the second stage, we shrink the borders of the remaining clusters by training a one-class SVM model on each cluster. To detected abnormal events in the test video, we analyze each test sample and consider its maximum normality score provided by the trained one-class SVM models, based on the intuition that a test sample can belong to only one cluster of normality. If the test sample does not fit well in any narrowed normality cluster, then it is labeled as abnormal. We compare our method with several state-of-the-art methods on three benchmark data sets. The empirical results indicate that our abnormal event detection framework can achieve better results in most cases, while processing the test video in real-time at 24 frames per second on a single CPU.
Privacy attitudes and concerns in the digital lives of older adults: Westin's privacy attitude typology revisited
Venue: arXiv cs.CY 2018
Year: 2018

There is a growing literature on teenage and young adult users' attitudes toward and concerns about online privacy, yet little is known about older adults and their unique experiences. As older adults join the digital world in growing numbers, we need to gain a better understanding of how they experience and navigate online privacy. This paper fills this research gap by examining 40 in-depth interviews with older adults (65 and older) living in East York, Toronto. We found Westin's typology to be a useful starting point for understanding privacy attitudes and concerns in this demographic. We expand Westin's typology and distinguish five categories: fundamentalist, intense pragmatist, relaxed pragmatist, marginally concerned, and cynical expert. We find that older adults are not a homogenous group composed of privacy fundamentalists; rather, there is considerable variability in terms of their privacy attitudes, with only 13 per cent being fundamentalists. We also identify a group of cynical experts who believe that online privacy breaches are inevitable. A large majority of older adults are marginally concerned, as they see their online participation as limited and harmless. Older adults were also grouped as either intense or relaxed pragmatists. We find that some privacy concerns are shared by older adults across several categories, the most common being spam, unauthorized access to personal information, and information misuse. We discuss theoretical implications based on the findings for our understanding of privacy in the context of older adults' digital lives and discuss implications for offering training appropriate for enhancing privacy literacy in this age group.
Toward Metric Indexes for Incremental Insertion and Querying
Venue: arXiv cs.DS 2018
Year: 2018

In this work we explore the use of metric index structures, which accelerate nearest neighbor queries, in the scenario where we need to interleave insertions and queries during deployment. This use-case is inspired by a real-life need in malware analysis triage, and is surprisingly understudied. Existing literature tends to either focus on only final query efficiency, often does not support incremental insertion, or does not support arbitrary distance metrics. We modify and improve three algorithms to support our scenario of incremental insertion and querying with arbitrary metrics, and evaluate them on multiple datasets and distance metrics while varying the value of $k$ for the desired number of nearest neighbors. In doing so we determine that our improved Vantage-Point tree of Minimum-Variance performs best for this scenario.
Excuse me! Perception of Abrupt Direction Changes Using Body Cues and Paths on Mixed Reality Avatars
Venue: arXiv cs.HC 2018
Year: 2018

We evaluate two methods of signalling abrupt direction changes of a robotic platform using a Mixed Reality avatar. The "Body" method uses gaze, gesture and torso direction to point to upcoming waypoints. The "Path" method visualises the change in direction using an angled path on the ground. We compare these two methods using a controlled user study and show that each method has its strengths depending on the situation. Overall the "Path" method was slightly more accurate in communicating the direction change of the robot but participants overall preferred the "Body" method.
Real-time Road Traffic Information Detection Through Social Media
Venue: arXiv cs.CL 2018
Year: 2018

In current study, a mechanism to extract traffic related information such as congestion and incidents from textual data from the internet is proposed. The current source of data is Twitter. As the data being considered is extremely large in size automated models are developed to stream, download, and mine the data in real-time. Furthermore, if any tweet has traffic related information then the models should be able to infer and extract this data. Currently, the data is collected only for United States and a total of 120,000 geo-tagged traffic related tweets are extracted, while six million geo-tagged non-traffic related tweets are retrieved and classification models are trained. Furthermore, this data is used for various kinds of spatial and temporal analysis. A mechanism to calculate level of traffic congestion, safety, and traffic perception for cities in U.S. is proposed. Traffic congestion and safety rankings for the various urban areas are obtained and then they are statistically validated with existing widely adopted rankings. Traffic perception depicts the attitude and perception of people towards the traffic. It is also seen that traffic related data when visualized spatially and temporally provides the same pattern as the actual traffic flows for various urban areas. When visualized at the city level, it is clearly visible that the flow of tweets is similar to flow of vehicles and that the traffic related tweets are representative of traffic within the cities. With all the findings in current study, it is shown that significant amount of traffic related information can be extracted from Twitter and other sources on internet. Furthermore, Twitter and these data sources are freely available and are not bound by spatial and temporal limitations. That is, wherever there is a user there is a potential for data.
Reed-Muller Sequences for 5G Grant-free Massive Access
Venue: arXiv cs.IT 2018
Year: 2018

We propose to use second order Reed-Muller (RM) sequence for user identification in 5G grant-free access. The benefits of RM sequences mainly lie in two folds, (i) support of much larger user space, hence lower collision probability and (ii) lower detection complexity. These two features are essential to meet the massive connectivity ($10^7$ links/km$^2$), ultra-reliable and low-latency requirements in 5G, e.g., one-shot transmission ($\leq 1$ms) with $\leq 10^{-4}$ packet error rate. However, the non-orthogonality introduced during sequence space expansion leads to worse detection performance. In this paper, we propose a noise-resilient detection algorithm along with a layered sequence construction to meet the harsh requirements. Link-level simulations in both narrow-band and OFDM-based scenarios show that RM sequences are suitable for 5G.
Learning to Navigate: Exploiting Deep Networks to Inform Sample-Based Planning During Vision-Based Navigation
Venue: arXiv cs.RO 2018
Year: 2018

Recent applications of deep learning to navigation have generated end-to-end navigation solutions whereby visual sensor input is mapped to control signals or to motion primitives. The resulting visual navigation strategies work very well at collision avoidance and have performance that matches traditional reactive navigation algorithms while operating in real-time. It is accepted that these solutions cannot provide the same level of performance as a global planner. However, it is less clear how such end-to-end systems should be integrated into a full navigation pipeline. We evaluate the typical end-to-end solution within a full navigation pipeline in order to expose its weaknesses. Doing so illuminates how to better integrate deep learning methods into the navigation pipeline. In particular, we show that they are an efficient means to provide informed samples for sample-based planners. Controlled simulations with comparison against traditional planners show that the number of samples can be reduced by an order of magnitude while preserving navigation performance. Implementation on a mobile robot matches the simulated performance outcomes.