OpenRaiser/Intern-Atlas huggingface dataset:
Fairest Constant Sum-rate Transmission for Cooperative Data Exchange: An M-convex Minimization Approach
Venue: arXiv cs.IT 2015
Year: 2015

We consider the fairness in cooperative data exchange (CDE) problem among a set of wireless clients. In this system, each client initially obtains a subset of the packets. They exchange packets in order to reconstruct the entire packet set. We study the problem of how to find a transmission strategy that distributes the communication load most evenly in all strategies that have the same sum-rate (the total number of transmissions) and achieve universal recovery (the situation when all clients recover the packet set). We formulate this problem by a discrete minimization problem and prove its $M$-convexity. We show that our results can also be proved by the submodularity of the feasible region shown in previous works and are closely related to the resource allocation problems under submodular constraints. To solve this problem, we propose to use a steepest descent algorithm (SDA) based on $M$-convexity. By varying the number of clients and packets, we compare SDA with a deterministic algorithm (DA) based on submodularity in terms of convergence performance and complexity. The results show that for the problem of finding the fairest and minimum sum-rate strategy for the CDE problem SDA is more efficient than DA when the number of clients is up to five.
Web spam classification using supervised artificial neural network algorithms
Venue: arXiv cs.NE 2015
Year: 2015

Due to the rapid growth in technology employed by the spammers, there is a need of classifiers that are more efficient, generic and highly adaptive. Neural Network based technologies have high ability of adaption as well as generalization. As per our knowledge, very little work has been done in this field using neural network. We present this paper to fill this gap. This paper evaluates performance of three supervised learning algorithms of artificial neural network by creating classifiers for the complex problem of latest web spam pattern classification. These algorithms are Conjugate Gradient algorithm, Resilient Backpropagation learning, and Levenberg-Marquardt algorithm.
Activity recognition for a smartphone and web based travel survey
Venue: arXiv cs.CY 2015
Year: 2015

In transport modeling and prediction, trip purposes play an important role since mobility choices (e.g. modes, routes, departure times) are made in order to carry out specific activities. Activity based models, which have been gaining popularity in recent years, are built from a large number of observed trips and their purposes. However, data acquired through traditional interview-based travel surveys lack the accuracy and quantity required by such models. Smartphones and interactive web interfaces have emerged as an attractive alternative to conventional travel surveys. A smartphone-based travel survey, Future Mobility Survey (FMS), was developed and field-tested in Singapore and collected travel data from more than 1000 participants for multiple days. To provide a more intelligent interface, inferring the activities of a user at a certain location is a crucial challenge. This paper presents a learning model that infers the most likely activity associated to a certain visited place. The data collected in FMS contain errors or noise due to various reasons, so a robust approach via ensemble learning is used to improve generalization performance. Our model takes advantage of cross-user historical data as well as user-specific information, including socio-demographics. Our empirical results using FMS data demonstrate that the proposed method contributes significantly to our travel survey application.
Axiomatizing Lüttgen and Vogler's ready simulation for finite processes in $\text{CLL}_R$
Venue: arXiv cs.LO 2015
Year: 2015

In the framework of logic labelled transition system, a variant of weak ready simulation has been presented by Lüttgen and Vogler. It has been shown that such behavioural preorder is the largest precongruence w.r.t parallel and conjunction composition satisfying desired properties. This paper offers a ground-complete axiomatization for this precongruence over processes containing no recursion in the calculus $\text{CLL}_R$. Compared with usual inference system for process calculus, in addition to axioms about process operators, such system contains a number of axioms to characterize the interaction between process operators and logical operators.
Over-Sampling in a Deep Neural Network
Venue: arXiv cs.LG 2015
Year: 2015

Deep neural networks (DNN) are the state of the art on many engineering problems such as computer vision and audition. A key factor in the success of the DNN is scalability - bigger networks work better. However, the reason for this scalability is not yet well understood. Here, we interpret the DNN as a discrete system, of linear filters followed by nonlinear activations, that is subject to the laws of sampling theory. In this context, we demonstrate that over-sampled networks are more selective, learn faster and learn more robustly. Our findings may ultimately generalize to the human brain.
Provably weak instances of Ring-LWE
Venue: arXiv cs.CR 2015
Year: 2015

The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [Eisenträger-Hallgren-Lauter]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-$2$ cyclotomic fields, presented using the minimal polynomial of $ζ_{2^n} \pm 1$.
Optimal sequential fingerprinting: Wald vs. Tardos
Venue: arXiv cs.CR 2015
Year: 2015

We study sequential collusion-resistant fingerprinting, where the fingerprinting code is generated in advance but accusations may be made between rounds, and show that in this setting both the dynamic Tardos scheme and schemes building upon Wald's sequential probability ratio test (SPRT) are asymptotically optimal. We further compare these two approaches to sequential fingerprinting, highlighting differences between the two schemes. Based on these differences, we argue that Wald's scheme should in general be preferred over the dynamic Tardos scheme, even though both schemes have their merits. As a side result, we derive an optimal sequential group testing method for the classical model, which can easily be generalized to different group testing models.
A two-stage video coding framework with both self-adaptive redundant dictionary and adaptively orthonormalized DCT basis
Venue: arXiv cs.MM 2015
Year: 2015

In this work, we propose a two-stage video coding framework, as an extension of our previous one-stage framework in [1]. The two-stage frameworks consists two different dictionaries. Specifically, the first stage directly finds the sparse representation of a block with a self-adaptive dictionary consisting of all possible inter-prediction candidates by solving an L0-norm minimization problem using an improved orthogonal matching pursuit with embedded orthonormalization (eOMP) algorithm, and the second stage codes the residual using DCT dictionary adaptively orthonormalized to the subspace spanned by the first stage atoms. The transition of the first stage and the second stage is determined based on both stages' quantization stepsizes and a threshold. We further propose a complete context adaptive entropy coder to efficiently code the locations and the coefficients of chosen first stage atoms. Simulation results show that the proposed coder significantly improves the RD performance over our previous one-stage coder. More importantly, the two-stage coder, using a fixed block size and inter-prediction only, outperforms the H.264 coder (x264) and is competitive with the HEVC reference coder (HM) over a large rate range.
Achieving Max-Min Fairness for MU-MISO with Partial CSIT: A Multicast Assisted Transmission
Venue: arXiv cs.IT 2015
Year: 2015

We address the max-min fairness design problem for a MU-MISO system with partial Channel State Information (CSI) at the Base Station (BS), consisting of an imperfect channel estimate and statistical knowledge of the estimation error, and perfect CSI at the receivers. The objective is to maximize the minimum Average Rate (AR) among users subject to a transmit power constraint. An unconventional transmission scheme is adopted where the Base Station (BS) transmits a common message in addition to the conventional private messages. In situations where the CSIT is not accurate enough to perform interference nulling, individual rates are assisted by allocating parts of the common message to different users according to their needs. The AR problem is transformed into an augmented Average Weighted Mean Square Error (AWMSE) problem, solved using Alternating Optimization (AO). The benefits of incorporating the common message are demonstrated through simulations.
Gradient Difference based approach for Text Localization in Compressed domain
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a gradient difference based approach to text localization in videos and scene images. The input video frame/ image is first compressed using multilevel 2-D wavelet transform. The edge information of the reconstructed image is found which is further used for finding the maximum gradient difference between the pixels and then the boundaries of the detected text blocks are computed using zero crossing technique. We perform logical AND operation of the text blocks obtained by gradient difference and the zero crossing technique followed by connected component analysis to eliminate the false positives. Finally, the morphological dilation operation is employed on the detected text blocks for scene text localization. The experimental results obtained on publicly available standard datasets illustrate that the proposed method can detect and localize the texts of various sizes, fonts and colors.
Parameterized Complexity of Secluded Connectivity Problems
Venue: arXiv cs.DS 2015
Year: 2015

The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure of the tree is minimized. The problems were introduced by Chechik et al. in [ESA 2013]. Among other results, Chechik et al. have shown that Secluded Path is fixed-parameter tractable (FPT) on unweighted graphs being parameterized by the maximum vertex degree of the graph and that Secluded Steiner Tree is FPT parameterized by the treewidth of the graph. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We give FPT-algorithms deciding if a graph G with a given cost function contains a secluded path and a secluded Steiner tree of exposure at most k with the cost at most C. We initiate the study of "above guarantee" parameterizations for secluded problems, where the lower bound is given by the size of a Steiner tree. We investigate Secluded Steiner Tree from kernelization perspective and provide several lower and upper bounds when parameters are the treewidth, the size of a vertex cover, maximum vertex degree and the solution size. Finally, we refine the algorithmic result of Chechik et al. by improving the exponential dependence from the treewidth of the input graph.
Local Computation Algorithms for Graphs of Non-Constant Degrees
Venue: arXiv cs.DS 2015
Year: 2015

In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on $n$, the number of vertices. Nonetheless, these complexities are generally at least exponential in $d$, the upper bound on the degree of the input graph. Instead, we consider the case where parameter $d$ can be moderately dependent on $n$, and aim for complexities with subexponential dependence on $d$, while maintaining polylogarithmic dependence on $n$. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in $d$ and polylogarithmic in $n$; for constant $ε> 0$, a randomized LCA that provides a $(1-ε)$-approximation to maximum matching whose time and space complexities are polynomial in $d$ and polylogarithmic in $n$.
QPACE 2 and Domain Decomposition on the Intel Xeon Phi
Venue: arXiv cs.DC 2015
Year: 2015

We give an overview of QPACE 2, which is a custom-designed supercomputer based on Intel Xeon Phi processors, developed in a collaboration of Regensburg University and Eurotech. We give some general recommendations for how to write high-performance code for the Xeon Phi and then discuss our implementation of a domain-decomposition-based solver and present a number of benchmarks.
The Responsibility Weighted Mahalanobis Kernel for Semi-Supervised Training of Support Vector Machines for Classification
Venue: arXiv cs.LG 2015
Year: 2015

Kernel functions in support vector machines (SVM) are needed to assess the similarity of input samples in order to classify these samples, for instance. Besides standard kernels such as Gaussian (i.e., radial basis function, RBF) or polynomial kernels, there are also specific kernels tailored to consider structure in the data for similarity assessment. In this article, we will capture structure in data by means of probabilistic mixture density models, for example Gaussian mixtures in the case of real-valued input spaces. From the distance measures that are inherently contained in these models, e.g., Mahalanobis distances in the case of Gaussian mixtures, we derive a new kernel, the responsibility weighted Mahalanobis (RWM) kernel. Basically, this kernel emphasizes the influence of model components from which any two samples that are compared are assumed to originate (that is, the "responsible" model components). We will see that this kernel outperforms the RBF kernel and other kernels capturing structure in data (such as the LAP kernel in Laplacian SVM) in many applications where partially labeled data are available, i.e., for semi-supervised training of SVM. Other key advantages are that the RWM kernel can easily be used with standard SVM implementations and training algorithms such as sequential minimal optimization, and heuristics known for the parametrization of RBF kernels in a C-SVM can easily be transferred to this new kernel. Properties of the RWM kernel are demonstrated with 20 benchmark data sets and an increasing percentage of labeled samples in the training data.
Downlink Throughput Driven Channel Access Framework for Cognitive LTE Femto-Cells
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes an optimized sensing based channel access framework for the LTE cognitive femto-cells, with an objective of maximizing the femto-cells downlink throughput. Cognitive femto-cells opportunistically transmit on the macro-cell channels when they are free of use. Those free channels are located by means of spectrum sensing using energy detection. Moreover, periodic sensing is adopted to detect any changes of the sensing outcomes. The maximum attainable femto-cell downlink throughput varies with the macro-cell channel occupancy statistics. Therefore, the LTE macro-cell occupancy is empirically modeled using exponential distributions mixture. The LTE cognitive femto-cell downlink throughput is maximized by compromising the transmission efficiency, the explored spectrum opportunities and the interference from the macro-cell. An analytical solution for the optimal periodic sensing interval that maximizes the throughput is found and verified by simulations. The obtained results show that there is indeed a single periodic sensing interval value that maximizes the LTE cognitive femto-cell downlink throughput. At the peak of the macro-cell traffic, our framework increases the femto-cell throughput by around 15% compared to the senseless case. The impact of the available number of channels for opportunistic access is studied and no significant impact is found for more than three channels.
Sensor Assisted Movement Identification and Prediction for Beamformed 60 GHz Links: A Report
Venue: arXiv cs.NI 2015
Year: 2015

Large available bandwidth in 60\,GHz band promises very high data rates -- in the order of Gb/s. However, high free-space path loss makes it necessary to employ beamforming capable directional antennas. When beamforming is used, the links are sensitive to misalignment in antenna directionality because of movement of devices. To identify and circumvent the misalignments, we propose to use the motion sensors (i.e., accelerometer and gyroscope) which are already present in most of the modern mobile devices. By finding the extent of misaligned beams, corrective actions are carried out to reconfigure the antennas. Motion sensors on mobile devices provide means to estimate the extent of misalignments. We collected real data from motion sensors and steer the beams appropriately. The results from our study show that the sensors are capable of detecting the cause of errors as translational or rotational movements. Furthermore it is also shown that the sensor data can be used to predict the next location of the user. This can be used to reconfigure the directional antenna to switch the antenna beam directions and hence avoid frequent link disruptions. This decreases the number of beam searches thus lowering the MAC overhead.
The generalized Lasso with non-linear observations
Venue: arXiv cs.IT 2015
Year: 2015

We study the problem of signal estimation from non-linear observations when the signal belongs to a low-dimensional set buried in a high-dimensional space. A rough heuristic often used in practice postulates that non-linear observations may be treated as noisy linear observations, and thus the signal may be estimated using the generalized Lasso. This is appealing because of the abundance of efficient, specialized solvers for this program. Just as noise may be diminished by projecting onto the lower dimensional space, the error from modeling non-linear observations with linear observations will be greatly reduced when using the signal structure in the reconstruction. We allow general signal structure, only assuming that the signal belongs to some set K in R^n. We consider the single-index model of non-linearity. Our theory allows the non-linearity to be discontinuous, not one-to-one and even unknown. We assume a random Gaussian model for the measurement matrix, but allow the rows to have an unknown covariance matrix. As special cases of our results, we recover near-optimal theory for noisy linear observations, and also give the first theoretical accuracy guarantee for 1-bit compressed sensing with unknown covariance matrix of the measurement vectors.
Modeling Brain Circuitry over a Wide Range of Scales
Venue: arXiv cs.CV 2015
Year: 2015

If we are ever to unravel the mysteries of brain function at its most fundamental level, we will need a precise understanding of how its component neurons connect to each other. Electron Microscopes (EM) can now provide the nanometer resolution that is needed to image synapses, and therefore connections, while Light Microscopes (LM) see at the micrometer resolution required to model the 3D structure of the dendritic network. Since both the topology and the connection strength are integral parts of the brain's wiring diagram, being able to combine these two modalities is critically important. In fact, these microscopes now routinely produce high-resolution imagery in such large quantities that the bottleneck becomes automated processing and interpretation, which is needed for such data to be exploited to its full potential. In this paper, we briefly review the Computer Vision techniques we have developed at EPFL to address this need. They include delineating dendritic arbors from LM imagery, segmenting organelles from EM, and combining the two into a consistent representation.
Leader-follower Tracking Control with Guaranteed Consensus Performance for Interconnected Systems with Linear Dynamic Uncertain Coupling
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the leader-follower tracking control problem for linear interconnected systems with undirected topology and linear dynamic coupling. Interactions between the systems are treated as linear dynamic uncertainty and are described in terms of integral quadratic constraints (IQCs). A consensus-type tracking control protocol is proposed for each system based on its state relative its neighbors. In addition a selected set of subsystems uses for control their relative states with respect to the leader. Two methods are proposed for the design of this control protocol. One method uses a coordinate transformation to recast the protocol design problem as a decentralized robust control problem for an auxiliary interconnected large scale system. Another method is direct, it does not employ coordinate transformation; it also allows for more general linear uncertain interactions. Using these methods, sufficient conditions are obtained which guarantee that the system tracks the leader. These conditions guarantee a suboptimal bound on the system consensus and tracking performance. The proposed methods are compared using a simulation example, and their effectiveness is discussed. Also, algorithms are proposed for computing suboptimal controllers.
Grassmannian Codes as Lifts of Matrix Codes Derived as Images of Linear Block Codes over Finite Fields
Venue: arXiv cs.IT 2015
Year: 2015

Let $p$ be a prime such that $p \equiv 2$ or $3$ mod $5$. Linear block codes over the non-commutative matrix ring of $2 \times 2$ matrices over the prime field $GF(p)$ endowed with the Bachoc weight are derived as isometric images of linear block codes over the Galois field $GF(p^2)$ endowed with the Hamming metric. When seen as rank metric codes, this family of matrix codes satisfies the Singleton bound and thus are maximum rank distance codes, which are then lifted to form a special class of subspace codes, the Grassmannian codes, that meet the anticode bound. These so-called anticode-optimal Grassmannian codes are associated in some way with complete graphs. New examples of these maximum rank distance codes and anticode-optimal Grassmannian codes are given.