OpenRaiser/Intern-Atlas huggingface dataset:
Sampling Online Social Networks via Heterogeneous Statistics
Venue: arXiv cs.SI 2015
Year: 2015

Most sampling techniques for online social networks (OSNs) are based on a particular sampling method on a single graph, which is referred to as a statistics. However, various realizing methods on different graphs could possibly be used in the same OSN, and they may lead to different sampling efficiencies, i.e., asymptotic variances. To utilize multiple statistics for accurate measurements, we formulate a mixture sampling problem, through which we construct a mixture unbiased estimator which minimizes asymptotic variance. Given fixed sampling budgets for different statistics, we derive the optimal weights to combine the individual estimators; given fixed total budget, we show that a greedy allocation towards the most efficient statistics is optimal. In practice, the sampling efficiencies of statistics can be quite different for various targets and are unknown before sampling. To solve this problem, we design a two-stage framework which adaptively spends a partial budget to test different statistics and allocates the remaining budget to the inferred best statistics. We show that our two-stage framework is a generalization of 1) randomly choosing a statistics and 2) evenly allocating the total budget among all available statistics, and our adaptive algorithm achieves higher efficiency than these benchmark strategies in theory and experiment.
Efficient Blind Compressed Sensing Using Sparsifying Transforms with Convergence Guarantees and Application to MRI
Venue: arXiv cs.LG 2015
Year: 2015

Natural signals and images are well-known to be approximately sparse in transform domains such as Wavelets and DCT. This property has been heavily exploited in various applications in image processing and medical imaging. Compressed sensing exploits the sparsity of images or image patches in a transform domain or synthesis dictionary to reconstruct images from undersampled measurements. In this work, we focus on blind compressed sensing, where the underlying sparsifying transform is a priori unknown, and propose a framework to simultaneously reconstruct the underlying image as well as the sparsifying transform from highly undersampled measurements. The proposed block coordinate descent type algorithms involve highly efficient optimal updates. Importantly, we prove that although the proposed blind compressed sensing formulations are highly nonconvex, our algorithms are globally convergent (i.e., they converge from any initialization) to the set of critical points of the objectives defining the formulations. These critical points are guaranteed to be at least partial global and partial local minimizers. The exact point(s) of convergence may depend on initialization. We illustrate the usefulness of the proposed framework for magnetic resonance image reconstruction from highly undersampled k-space measurements. As compared to previous methods involving the synthesis dictionary model, our approach is much faster, while also providing promising reconstruction quality.
Programming and Reasoning with Guarded Recursion for Coinductive Types
Venue: arXiv cs.PL 2015
Year: 2015

We present the guarded lambda-calculus, an extension of the simply typed lambda-calculus with guarded recursive and coinductive types. The use of guarded recursive types ensures the productivity of well-typed programs. Guarded recursive types may be transformed into coinductive types by a type-former inspired by modal logic and Atkey-McBride clock quantification, allowing the typing of acausal functions. We give a call-by-name operational semantics for the calculus, and define adequate denotational semantics in the topos of trees. The adequacy proof entails that the evaluation of a program always terminates. We demonstrate the expressiveness of the calculus by showing the definability of solutions to Rutten's behavioural differential equations. We introduce a program logic with Löb induction for reasoning about the contextual equivalence of programs.
Complexity of Power Draws for Load Disaggregation
Venue: arXiv cs.OH 2015
Year: 2015

Non-Intrusive Load Monitoring (NILM) is a technology offering methods to identify appliances in homes based on their consumption characteristics and the total household demand. Recently, many different novel NILM approaches were introduced, tested on real-world data and evaluated with a common evaluation metric. However, the fair comparison between different NILM approaches even with the usage of the same evaluation metric is nearly impossible due to incomplete or missing problem definitions. Each NILM approach typically is evaluated under different test scenarios. Test results are thus influenced by the considered appliances, the number of used appliances, the device type representing the appliance and the pre-processing stages denoising the consumption data. This paper introduces a novel complexity measure of aggregated consumption data providing an assessment of the problem complexity affected by the used appliances, the appliance characteristics and the appliance usage over time. We test our load disaggregation complexity on different real-world datasets and with a state-of-the-art NILM approach. The introduced disaggregation complexity measure is able to classify the disaggregation problem based on the used appliance set and the considered measurement noise.
An Adaptive Neuro-Fuzzy Inference System Modeling for Grid-Adaptive Interpolation over Depth Images
Venue: arXiv cs.CV 2015
Year: 2015

A suitable interpolation method is essential to keep the noise level minimum along with the time-delay. In recent years, many different interpolation filters have been developed for instance H.264-6 tap filter, and AVS- 4 tap filter. The present work uses Adaptive Neuro-Fuzzy Inference System (ANFIS) technique to model and investigate the effects of a four-tap low-pass tap filter (Grid-adaptive filter) on a hole-filled depth image. The work demonstrates the general form of uniform interpolations for both integer and sub-pixel locations in terms of the sampling interval and filter length of depth-images via diverse finite impulse response filtering schemes. The demonstrated model combined modelling function of fuzzy inference with the learning ability of artificial neural network.
Learning from Multiple Sources for Video Summarisation
Venue: arXiv cs.CV 2015
Year: 2015

Many visual surveillance tasks, e.g.video summarisation, is conventionally accomplished through analysing imagerybased features. Relying solely on visual cues for public surveillance video understanding is unreliable, since visual observations obtained from public space CCTV video data are often not sufficiently trustworthy and events of interest can be subtle. On the other hand, non-visual data sources such as weather reports and traffic sensory signals are readily accessible but are not explored jointly to complement visual data for video content analysis and summarisation. In this paper, we present a novel unsupervised framework to learn jointly from both visual and independently-drawn non-visual data sources for discovering meaningful latent structure of surveillance video data. In particular, we investigate ways to cope with discrepant dimension and representation whist associating these heterogeneous data sources, and derive effective mechanism to tolerate with missing and incomplete data from different sources. We show that the proposed multi-source learning framework not only achieves better video content clustering than state-of-the-art methods, but also is capable of accurately inferring missing non-visual semantics from previously unseen videos. In addition, a comprehensive user study is conducted to validate the quality of video summarisation generated using the proposed multi-source model.
Deep Learning with Nonparametric Clustering
Venue: arXiv cs.LG 2015
Year: 2015

Clustering is an essential problem in machine learning and data mining. One vital factor that impacts clustering performance is how to learn or design the data representation (or features). Fortunately, recent advances in deep learning can learn unsupervised features effectively, and have yielded state of the art performance in many classification problems, such as character recognition, object recognition and document categorization. However, little attention has been paid to the potential of deep learning for unsupervised clustering problems. In this paper, we propose a deep belief network with nonparametric clustering. As an unsupervised method, our model first leverages the advantages of deep learning for feature representation and dimension reduction. Then, it performs nonparametric clustering under a maximum margin framework -- a discriminative clustering model and can be trained online efficiently in the code space. Lastly model parameters are refined in the deep belief network. Thus, this model can learn features for clustering and infer model complexity in an unified framework. The experimental results show the advantage of our approach over competitive baselines.
Robust and Real Time Detection of Curvy Lanes (Curves) with Desired Slopes for Driving Assistance and Autonomous Vehicles
Venue: arXiv cs.CV 2015
Year: 2015

One of the biggest reasons for road accidents is curvy lanes and blind turns. Even one of the biggest hurdles for new autonomous vehicles is to detect curvy lanes, multiple lanes and lanes with a lot of discontinuity and noise. This paper presents very efficient and advanced algorithm for detecting curves having desired slopes (especially for detecting curvy lanes in real time) and detection of curves (lanes) with a lot of noise, discontinuity and disturbances. Overall aim is to develop robust method for this task which is applicable even in adverse conditions. Even in some of most famous and useful libraries like OpenCV and Matlab, there is no function available for detecting curves having desired slopes , shapes, discontinuities. Only few predefined shapes like circle, ellipse, etc, can be detected using presently available functions. Proposed algorithm can not only detect curves with discontinuity, noise, desired slope but also it can perform shadow and illumination correction and detect/ differentiate between different curves.
Video Manipulation Techniques for the Protection of Privacy in Remote Presence Systems
Venue: arXiv cs.RO 2015
Year: 2015

Systems that give control of a mobile robot to a remote user raise privacy concerns about what the remote user can see and do through the robot. We aim to preserve some of that privacy by manipulating the video data that the remote user sees. Through two user studies, we explore the effectiveness of different video manipulation techniques at providing different types of privacy. We simultaneously examine task performance in the presence of privacy protection. In the first study, participants were asked to watch a video captured by a robot exploring an office environment and to complete a series of observational tasks under differing video manipulation conditions. Our results show that using manipulations of the video stream can lead to fewer privacy violations for different privacy types. Through a second user study, it was demonstrated that these privacy-protecting techniques were effective without diminishing the task performance of the remote user.
Forward Delay-based Packet Scheduling Algorithm for Multipath TCP
Venue: arXiv cs.NI 2015
Year: 2015

Multipath TCP (MPTCP) is a transport layer protocol that allows network devices to transfer data over multiple concurrent paths, and hence, utilizes the network resources more effectively than does the traditional single-path TCP. However, as a reliable protocol, MPTCP still needs to deliver data packets (to the upper application) at the receiver in the same order they are transmitted at the sender. The out-of-order packet problem becomes more severe for MPTCP due to the heterogeneous nature of delay and bandwidth of each path. In this paper, we propose the forward-delay-based packet scheduling (FDPS) algorithm for MPTCP to address that problem. The main idea is that the sender dispatches packets via concurrent paths according to their estimated forward delay and throughput differences. Via simulations with various network conditions, the results show that our algorithm significantly maintains in-order arrival packets at the receiver compared with several previous algorithms.
Compressive Sensing with Redundant Dictionaries and Structured Measurements
Venue: arXiv cs.IT 2015
Year: 2015

Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary $D$. This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary, if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the $D$-restricted isometry property ($D$-RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in $D$. While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the $D$-RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary $D$. We also extend this analysis to allow for weighted sparse expansions. Consequently, we arrive at compressive sensing recovery guarantees for structured measurements and redundant dictionaries, opening the door to a wide array of practical applications.
Successive Cancellation Decoding of Polar Codes using Stochastic Computing
Venue: arXiv cs.IT 2015
Year: 2015

Polar codes have emerged as the most favorable channel codes for their unique capacity-achieving property. To date, numerous works have been reported for efficient design of polar codes decoder. However, these prior efforts focused on design of polar decoders via deterministic computation, while the behavior of stochastic polar decoder, which can have potential advantages such as low complexity and strong error-resilience, has not been studied in existing literatures. This paper, for the first time, investigates polar decoding using stochastic logic. Specifically, the commonly-used successive cancellation (SC) algorithm is reformulated into the stochastic form. Several methods that can potentially improve decoding performance are discussed and analyzed. Simulation results show that a stochastic SC decoder can achieve similar error-correcting performance as its deterministic counterpart. This work can pave the way for future hardware design of stochastic polar codes decoders.
Sequent Calculus in the Topos of Trees
Venue: arXiv cs.LO 2015
Year: 2015

Nakano's "later" modality, inspired by Gödel-Löb provability logic, has been applied in type systems and program logics to capture guarded recursion. Birkedal et al modelled this modality via the internal logic of the topos of trees. We show that the semantics of the propositional fragment of this logic can be given by linear converse-well-founded intuitionistic Kripke frames, so this logic is a marriage of the intuitionistic modal logic KM and the intermediate logic LC. We therefore call this logic $\mathrm{KM}_{\mathrm{lin}}$. We give a sound and cut-free complete sequent calculus for $\mathrm{KM}_{\mathrm{lin}}$ via a strategy that decomposes implication into its static and irreflexive components. Our calculus provides deterministic and terminating backward proof-search, yields decidability of the logic and the coNP-completeness of its validity problem. Our calculus and decision procedure can be restricted to drop linearity and hence capture KM.
Complete analytic solution to Brownian unicycle dynamics
Venue: arXiv cs.RO 2015
Year: 2015

This paper derives a complete analytical solution for the probability distribution of the configuration of a non-holonomic vehicle that moves in two spatial dimensions by satisfying the unicycle kinematic constraints and in presence of Brownian noises. In contrast to previous solutions, the one here derived holds even in the case of arbitrary linear and angular speed. This solution is obtained by deriving the analytical expression of any-order moment of the probability distribution. To the best of our knowledge, an analytical expression for any-order moment that holds even in the case of arbitrary linear and angular speed, has never been derived before. To compute these moments, a direct integration of the Langevin equation is carried out and each moment is expressed as a multiple integral of the deterministic motion (i.e., the known motion that would result in absence of noise). For the special case when the ratio between the linear and angular speed is constant, the multiple integrals can be easily solved and expressed as the real or the imaginary part of suitable analytic functions. As an application of the derived analytical results, the paper investigates the diffusivity of the considered Brownian motion for constant and for arbitrary time-dependent linear and angular speed.
The potential and challenges of Big data - Recommendation systems next level application
Venue: arXiv cs.CY 2015
Year: 2015

The continuous increase of data generated provides enormous possibilities of both public and private companies. The management of this mass of data or big data will play a crucial role in the society of the future, as it finds applications in different fields. There are so much potential and extremely useful insights hidden in the huge volume of data. The advanced analysis techniques available including predictive analytics, text mining, semantic analysis are needed to enable organizations to create a competitive advantage through data analyzed with different levels of sophistication, speed and accuracy previously unavailable. Therefore, is it still possible to have that level of sophistication with the ubiquitous numeric ocean that accompanies use every day via connected devices that invade our lives? However, development of big data requires a good understanding of the issues associated with it. And this is the purpose of this paper, which focuses on giving a close-up view of big data analysis, opportunities and challenges.
A Superintroduction to Google Matrices for Undergraduates
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we consider so-called Google matrices and show that all eigenvalues ($λ$) of them have a fundamental property $|λ|\leq 1$. The stochastic eigenvector corresponding to $λ=1$ called the PageRank vector plays a central role in the Google's software. We study it in detail and present some important problems. The purpose of the paper is to make {\bf the heart of Google} clearer for undergraduates.
Iso-Quality of Service: Fairly Ranking Servers for Real-Time Data Analytics
Venue: arXiv cs.DC 2015
Year: 2015

We present a mathematically rigorous Quality-of-Service (QoS) metric which relates the achievable quality of service metric (QoS) for a real-time analytics service to the server energy cost of offering the service. Using a new iso-QoS evaluation methodology, we scale server resources to meet QoS targets and directly rank the servers in terms of their energy-efficiency and by extension cost of ownership. Our metric and method are platform-independent and enable fair comparison of datacenter compute servers with significant architectural diversity, including micro-servers. We deploy our metric and methodology to compare three servers running financial option pricing workloads on real-life market data. We find that server ranking is sensitive to data inputs and desired QoS level and that although scale-out micro-servers can be up to two times more energy-efficient than conventional heavyweight servers for the same target QoS, they are still six times less energy efficient than high-performance computational accelerators.
Secrecy Through Synchronization Errors
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a transmission scheme that achieves information theoretic security, without making assumptions on the eavesdropper's channel. This is achieved by a transmitter that deliberately introduces synchronization errors (insertions and/or deletions) based on a shared source of randomness. The intended receiver, having access to the same shared source of randomness as the transmitter, can resynchronize the received sequence. On the other hand, the eavesdropper's channel remains a synchronization error channel. We prove a secrecy capacity theorem, provide a lower bound on the secrecy capacity, and propose numerical methods to evaluate it.
Consistence beats causality in recommender systems
Venue: arXiv cs.IR 2015
Year: 2015

The explosive growth of information challenges people's capability in finding out items fitting to their own interests. Recommender systems provide an efficient solution by automatically push possibly relevant items to users according to their past preferences. Recommendation algorithms usually embody the causality from what having been collected to what should be recommended. In this article, we argue that in many cases, a user's interests are stable, and thus the previous and future preferences are highly consistent. The temporal order of collections then does not necessarily imply a causality relationship. We further propose a consistence-based algorithm that outperforms the state-of-the-art recommendation algorithms in disparate real data sets, including \textit{Netflix}, \textit{MovieLens}, \textit{Amazon} and \textit{Rate Your Music}.
Equation $x^iy^jx^k=u^iv^ju^k$ in words
Venue: arXiv cs.FL 2015
Year: 2015

We will prove that the word $a^ib^ja^k$ is periodicity forcing if $j \geq 3$ and $i+k \geq 3$, where $i$ and $k$ are positive integers. Also we will give examples showing that both bounds are optimal.
Random Cell Association and Void Probability in Poisson-Distributed Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper studied the fundamental modeling defect existing in Poisson-distributed cellular networks in which all base stations form a homogeneous Poisson point process (PPP) of intensity $λ_B$ and all users form another independent PPP of intensity $λ_U$. The modeling defect, hardly discovered in prior works, is the void cell issue that stems from the independence between the distributions of users and BSs and "user-centric" cell association, and it could give rise to very inaccurate analytical results. We showed that the void probability of a cell under generalized random cell association is always bounded above zero and its theoretical lower bound is $\exp(-\frac{λ_U}{λ_B})$ that can be achieved by large association weighting. An accurate expression of the void probability of a cell was derived and simulation results validated its correctness. We also showed that the associated BSs are essentially no longer a PPP such that modeling them as a PPP to facilitate the analysis of interference-related performance metrics may detach from reality if the BS intensity is not significantly large if compared with the user intensity.