OpenRaiser/Intern-Atlas huggingface dataset:
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
Venue: arXiv cs.GT 2014
Year: 2014

In this paper, we introduce a novel approach for reducing the $k$-item $n$-bidder auction with additive valuation to $k$-item $1$-bidder auctions. This approach, called the \emph{Best-Guess} reduction, can be applied to address several central questions in optimal revenue auction theory such as the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called {\it Deterministic Best-Guess} that yields at least a constant fraction of the optimal revenue by any randomized mechanism. Second, if all the $nk$ valuation random variables are independent, the optimal revenue achievable in {\it dominant strategy incentive compatibility} (DSIC) is shown to be at least a constant fraction of that achievable in {\it Bayesian incentive compatibility} (BIC). Third, when all the $nk$ values are identically distributed according to a common one-dimensional distribution $F$, the optimal revenue is shown to be expressible in the closed form $Θ(k(r+\int_0^{mr} (1-F(x)^n) \ud x))$ where $r= sup_{x\geq 0} \, x(1 - F(x)^n)$ and $m=\lceil k/n\rceil$; this revenue is achievable by a simple mechanism called \emph{2nd-Price Bundling}. All our results apply to arbitrary distributions, regular or irregular.
Indeterminate Strings, Prefix Arrays & Undirected Graphs
Venue: arXiv cs.DM 2014
Year: 2014

An integer array y = y[1..n] is said to be feasible if and only if y[1] = n and, for every i \in 2..n, i \le i+y[i] \le n+1. A string is said to be indeterminate if and only if at least one of its elements is a subset of cardinality greater than one of a given alphabet Sigma; otherwise it is said to be regular. A feasible array y is said to be regular if and only if it is the prefix array of some regular string. We show using a graph model that every feasible array of integers is a prefix array of some (indeterminate or regular) string, and for regular strings corresponding to y, we use the model to provide a lower bound on the alphabet size. We show further that there is a 1-1 correspondence between labelled simple graphs and indeterminate strings, and we show how to determine the minimum alphabet size |Sigma| of an indeterminate string x based on its associated graph Gx. Thus, in this sense, indeterminate strings are a more natural object of combinatorial interest than the strings on elements of Sigma that have traditionally been studied.
Stable, Robust and Super Fast Reconstruction of Tensors Using Multi-Way Projections
Venue: arXiv cs.IT 2014
Year: 2014

In the framework of multidimensional Compressed Sensing (CS), we introduce an analytical reconstruction formula that allows one to recover an $N$th-order $(I_1\times I_2\times \cdots \times I_N)$ data tensor $\underline{\mathbf{X}}$ from a reduced set of multi-way compressive measurements by exploiting its low multilinear-rank structure. Moreover, we show that, an interesting property of multi-way measurements allows us to build the reconstruction based on compressive linear measurements taken only in two selected modes, independently of the tensor order $N$. In addition, it is proved that, in the matrix case and in a particular case with $3$rd-order tensors where the same 2D sensor operator is applied to all mode-3 slices, the proposed reconstruction $\underline{\mathbf{X}}_τ$ is stable in the sense that the approximation error is comparable to the one provided by the best low-multilinear-rank approximation, where $τ$ is a threshold parameter that controls the approximation error. Through the analysis of the upper bound of the approximation error we show that, in the 2D case, an optimal value for the threshold parameter $τ=τ_0 > 0$ exists, which is confirmed by our simulation results. On the other hand, our experiments on 3D datasets show that very good reconstructions are obtained using $τ=0$, which means that this parameter does not need to be tuned. Our extensive simulation results demonstrate the stability and robustness of the method when it is applied to real-world 2D and 3D signals. A comparison with state-of-the-arts sparsity based CS methods specialized for multidimensional signals is also included. A very attractive characteristic of the proposed method is that it provides a direct computation, i.e. it is non-iterative in contrast to all existing sparsity based CS algorithms, thus providing super fast computations, even for large datasets.
Analysis of the Frequency Offset Effect on Zadoff-Chu Sequence Timing Performance
Venue: arXiv cs.NI 2014
Year: 2014

Zadoff-Chu (ZC) sequences have been used as synchronization sequences in modern wireless communication systems, replacing the conventional pseudo-random noise (PN) sequences due to their perfect autocorrelation properties. We first study the ambiguity problem between a timing offset and a frequency offset when a ZC sequence is used as a synchronization signal. We show how a frequency offset can impair the timing property of a ZC sequence, causing irreducible timing errors. An analytical framework is developed, which completely characterizes a ZC sequence's timing behavior and its fundamental limitation as a synchronization sequence in the presence of a frequency offset between the transmitter and the receiver.
Fingers' Angle Calculation using Level-Set Method
Venue: arXiv cs.CV 2014
Year: 2014

In the current age, use of natural communication in human computer interaction is a known and well installed thought. Hand gesture recognition and gesture based applications has gained a significant amount of popularity amongst people all over the world. It has a number of applications ranging from security to entertainment. These applications generally are real time applications and need fast, accurate communication with machines. On the other end, gesture based communications have few limitations also like bent finger information is not provided in vision based techniques. In this paper, a novel method for fingertip detection and for angle calculation of both hands bent fingers is discussed. Angle calculation has been done before with sensor based gloves/devices. This study has been conducted in the context of natural computing for calculating angles without using any wired equipment, colors, marker or any device. The pre-processing and segmentation of the region of interest is performed in a HSV color space and a binary format respectively. Fingertips are detected using level-set method and angles were calculated using geometrical analysis. This technique requires no training for system to perform the task.
A Model for Variation- and Fault-Tolerant Digital Logic using Self-Assembled Nanowire Architectures
Venue: arXiv cs.ET 2014
Year: 2014

Reconfiguration has been used for both defect- and fault-tolerant nanoscale architectures with regular structure. Recent advances in self-assembled nanowires have opened doors to a new class of electronic devices with irregular structure. For such devices, reservoir computing has been shown to be a viable approach to implement computation. This approach exploits the dynamical properties of a system rather than specifics of its structure. Here, we extend a model of reservoir computing, called the echo state network, to reflect more realistic aspects of self-assembled nanowire networks. As a proof of concept, we use echo state networks to implement basic building blocks of digital computing: AND, OR, and XOR gates, and 2-bit adder and multiplier circuits. We show that the system can operate perfectly in the presence of variations five orders of magnitude higher than ITRS's 2005 target, $\bm{6\%}$, and achieves success rates $\bm{6}$ times higher than related approaches at half the cost. We also describe an adaptive algorithm that can detect faults in the system and reconfigure it to resume perfect operational condition.
On the Linear Programming Bound for Lee-codes
Venue: arXiv cs.IT 2014
Year: 2014

Finding the largest code with a given minimum distance is one of the most basic problems in coding theory. In this paper, we study the linear programming bound for codes in the Lee metric. We introduce refinements on the linear programming bound for linear codes in the Lee metric, which give a tighter bound for linear codes. We also discuss the computational aspects of the problem and introduce a more compact program by the obtained refinements, and a recursive method for computing the so-called Lee-numbers, which are important in the computation of the linear programming bound.
Lightening Global Types
Venue: arXiv cs.PL 2014
Year: 2014

Global session types prevent participants from waiting for never coming messages. Some interactions take place just for the purpose of informing receivers that some message will never arrive or the session is terminated. By decomposing a big global type into several light global types, one can avoid such kind of redundant interactions. Lightening global types gives us cleaner global types, which keep all necessary communications. This work proposes a framework which allows to easily decompose global types into light global types, preserving the interaction sequences of the original ones but for redundant interactions.
EigenEvent: An Algorithm for Event Detection from Complex Data Streams in Syndromic Surveillance
Venue: arXiv cs.AI 2014
Year: 2014

Syndromic surveillance systems continuously monitor multiple pre-diagnostic daily streams of indicators from different regions with the aim of early detection of disease outbreaks. The main objective of these systems is to detect outbreaks hours or days before the clinical and laboratory confirmation. The type of data that is being generated via these systems is usually multivariate and seasonal with spatial and temporal dimensions. The algorithm What's Strange About Recent Events (WSARE) is the state-of-the-art method for such problems. It exhaustively searches for contrast sets in the multivariate data and signals an alarm when find statistically significant rules. This bottom-up approach presents a much lower detection delay comparing the existing top-down approaches. However, WSARE is very sensitive to the small-scale changes and subsequently comes with a relatively high rate of false alarms. We propose a new approach called EigenEvent that is neither fully top-down nor bottom-up. In this method, we instead of top-down or bottom-up search, track changes in data correlation structure via eigenspace techniques. This new methodology enables us to detect both overall changes (via eigenvalue) and dimension-level changes (via eigenvectors). Experimental results on hundred sets of benchmark data reveals that EigenEvent presents a better overall performance comparing state-of-the-art, in particular in terms of the false alarm rate.
Eigenspace Method for Spatiotemporal Hotspot Detection
Venue: arXiv cs.AI 2014
Year: 2014

Hotspot detection aims at identifying subgroups in the observations that are unexpected, with respect to the some baseline information. For instance, in disease surveillance, the purpose is to detect sub-regions in spatiotemporal space, where the count of reported diseases (e.g. Cancer) is higher than expected, with respect to the population. The state-of-the-art method for this kind of problem is the Space-Time Scan Statistics (STScan), which exhaustively search the whole space through a sliding window looking for significant spatiotemporal clusters. STScan makes some restrictive assumptions about the distribution of data, the shape of the hotspots and the quality of data, which can be unrealistic for some nontraditional data sources. A novel methodology called EigenSpot is proposed where instead of an exhaustive search over the space, tracks the changes in a space-time correlation structure. Not only does the new approach presents much more computational efficiency, but also makes no assumption about the data distribution, hotspot shape or the data quality. The principal idea is that with the joint combination of abnormal elements in the principal spatial and the temporal singular vectors, the location of hotspots in the spatiotemporal space can be approximated. A comprehensive experimental evaluation, both on simulated and real data sets reveals the effectiveness of the proposed method.
When relevance is not Enough: Promoting Visual Attractiveness for Fashion E-commerce
Venue: arXiv cs.HC 2014
Year: 2014

Fashion, and especially apparel, is the fastest-growing category in online shopping. As consumers requires sensory experience especially for apparel goods for which their appearance matters most, images play a key role not only in conveying crucial information that is hard to express in text, but also in affecting consumer's attitude and emotion towards the product. However, research related to e-commerce product image has mostly focused on quality at perceptual level, but not the quality of content, and the way of presenting. This study aims to address the effectiveness of types of image in showcasing fashion apparel in terms of its attractiveness, i.e. the ability to draw consumer's attention, interest, and in return their engagement. We apply advanced vision technique to quantize attractiveness using three common display types in fashion filed, i.e. human model, mannequin, and flat. We perform two-stage study by starting with large scale behavior data from real online market, then moving to well designed user experiment to further deepen our understandings on consumer's reasoning logic behind the action. We propose a Fisher noncentral hypergeometric distribution based user choice model to quantitatively evaluate user's preference. Further, we investigate the potentials to leverage visual impact for a better search that caters to user's preference. A visual attractiveness based re-ranking model that incorporates both presentation efficacy and user preference is proposed. We show quantitative improvement by promoting visual attractiveness into search on top of relevance.
Simulation of Pedestrian Movements Using Fine Grid Cellular Automata Model
Venue: arXiv cs.OH 2014
Year: 2014

Crowd simulation is used for evacuation and crowd safety inspections, study of performance in crowd systems and animations. Cellular automata has been extensively used in modelling the crowd. In regular cellular automata models, each pedestrian occupies a single cell with the size of a pedestrian body. Since the space is divided into relatively large cells, the movements of pedestrians look like the movements of pieces on a chess board. Furthermore, all pedestrians have the same body size and speed. In this paper, a method called fine grid cellular automata is proposed in which smaller cells are used and pedestrian body may occupy several cells. The model allows the use of different body sizes, shapes and speeds for pedestrian. The proposed model is used for simulating movements of pedestrians toward a target. A typical walkway scenario is used to test and evaluate the model. The movements of pedestrians are smoother because of the finer grain discretization of movements and the simulation results match empirical speed-density graphs with good accuracy.
Impact of Residual Transmit RF Impairments on Training-Based MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

Radio-frequency (RF) impairments, that exist intimately in wireless communications systems, can severely degrade the performance of traditional multiple-input multiple-output (MIMO) systems. Although compensation schemes can cancel out part of these RF impairments, there still remains a certain amount of impairments. These residual impairments have fundamental impact on the MIMO system performance. However, most of the previous works have neglected this factor. In this paper, a training-based MIMO system with residual transmit RF impairments (RTRI) is considered. In particular, we derive a new channel estimator for the proposed model, and find that RTRI can create an irreducible estimation error floor. Moreover, we show that, in the presence of RTRI, the optimal training sequence length can be larger than the number of transmit antennas, especially in the low and high signal-to-noise ratio (SNR) regimes. An increase in the proposed approximated achievable rate is also observed by adopting the optimal training sequence length. When the training and data symbol powers are required to be equal, we demonstrate that, at high SNRs, systems with RTRI demand more training, whereas at low SNRs, such demands are nearly the same for all practical levels of RTRI.
Component Based Software Development: A State of Art
Venue: arXiv cs.SE 2014
Year: 2014

One of the goals of Software design is to model a system in such a way that it is reused. Actively reusing designs or code allows taking advantage of the investment made on reusable components. However development of domain specific components and its impact on effort in terms of cost and time is still a challenging issue. The component based technology has transformed over a period of time from a simple component to the domain specific components. This paper presents a state of art of the drastic change in component technology from component engineering to domain engineering.
Smartphone sensing platform for emergency management
Venue: arXiv cs.CY 2014
Year: 2014

The increasingly sophisticated sensors supported by modern smartphones open up novel research opportunities, such as mobile phone sensing. One of the most challenging of these research areas is context-aware and activity recognition. The SmartRescue project takes advantage of smartphone sensing, processing and communication capabilities to monitor hazards and track people in a disaster. The goal is to help crisis managers and members of the public in early hazard detection, prediction, and in devising risk-minimizing evacuation plans when disaster strikes. In this paper we suggest a novel smartphone-based communication framework. It uses specific machine learning techniques that intelligently process sensor readings into useful information for the crisis responders. Core to the framework is a content-based publish-subscribe mechanism that allows flexible sharing of sensor data and computation results. We also evaluate a preliminary implementation of the platform, involving a smartphone app that reads and shares mobile phone sensor data for activity recognition.
Learning An Invariant Speech Representation
Venue: arXiv cs.SD 2014
Year: 2014

Recognition of speech, and in particular the ability to generalize and learn from small sets of labelled examples like humans do, depends on an appropriate representation of the acoustic input. We formulate the problem of finding robust speech features for supervised learning with small sample complexity as a problem of learning representations of the signal that are maximally invariant to intraclass transformations and deformations. We propose an extension of a theory for unsupervised learning of invariant visual representations to the auditory domain and empirically evaluate its validity for voiced speech sound classification. Our version of the theory requires the memory-based, unsupervised storage of acoustic templates -- such as specific phones or words -- together with all the transformations of each that normally occur. A quasi-invariant representation for a speech segment can be obtained by projecting it to each template orbit, i.e., the set of transformed signals, and computing the associated one-dimensional empirical probability distributions. The computations can be performed by modules of filtering and pooling, and extended to hierarchical architectures. In this paper, we apply a single-layer, multicomponent representation for phonemes and demonstrate improved accuracy and decreased sample complexity for vowel classification compared to standard spectral, cepstral and perceptual features.
Comments on "A New Method to Compute the 2-Adic Complexity of Binary Sequences"
Venue: arXiv cs.IT 2014
Year: 2014

We show that there is a very simple approach to determine the 2-adic complexity of periodic binary sequences with ideal two-level autocorrelation. This is the first main result by H. Xiong, L. Qu, and C. Li, IEEE Transactions on Information Theory, vol. 60, no. 4, pp. 2399-2406, Apr. 2014, and the main result by T. Tian and W. Qi, IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 450-454, Jan. 2010.
Bayesian Optimal Control of Smoothly Parameterized Systems: The Lazy Posterior Sampling Algorithm
Venue: arXiv cs.LG 2014
Year: 2014

We study Bayesian optimal control of a general class of smoothly parameterized Markov decision problems. Since computing the optimal control is computationally expensive, we design an algorithm that trades off performance for computational efficiency. The algorithm is a lazy posterior sampling method that maintains a distribution over the unknown parameter. The algorithm changes its policy only when the variance of the distribution is reduced sufficiently. Importantly, we analyze the algorithm and show the precise nature of the performance vs. computation tradeoff. Finally, we show the effectiveness of the method on a web server control application.
Maintaining Contour Trees of Dynamic Terrains
Venue: arXiv cs.CG 2014
Year: 2014

We consider maintaining the contour tree $\mathbb{T}$ of a piecewise-linear triangulation $\mathbb{M}$ that is the graph of a time varying height function $h: \mathbb{R}^2 \rightarrow \mathbb{R}$. We carefully describe the combinatorial change in $\mathbb{T}$ that happen as $h$ varies over time and how these changes relate to topological changes in $\mathbb{M}$. We present a kinetic data structure that maintains the contour tree of $h$ over time. Our data structure maintains certificates that fail only when $h(v)=h(u)$ for two adjacent vertices $v$ and $u$ in $\mathbb{M}$, or when two saddle vertices lie on the same contour of $\mathbb{M}$. A certificate failure is handled in $O(\log(n))$ time. We also show how our data structure can be extended to handle a set of general update operations on $\mathbb{M}$ and how it can be applied to maintain topological persistence pairs of time varying functions.
Mobile Communication Systems in the Presence of Fading/Shadowing, Noise and Interference
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the effects of interference on composite fading environments, where multipath fading coexists with shadowing, are investigated. Based on some mathematical convenient expressions for the sum of squared $\mathcal{K}$-distributed random variables, which are derived for the first time, important statistical metrics for the signal to interference and noise ratio (SINR) are studied for various cases including non identical, identical and fully correlated statistics. Furthermore, our analysis is extended to multi-channel receivers and in particular to selection diversity (SD) receivers, investigating two distinct cases, namely, signal-to-noise ratio based and SINR-based SD. For all scenarios, simplified expressions are also provided for the interference limited case, where the influence of thermal noise is ignored. The derived expressions are used to analyze the performance, in terms of the average bit error probability (ABEP) and the outage probability (OP), of such systems operating over composite fading environments. A high SNR analysis is also presented for the OP and the ABEP, giving a clear physical insight of the system's performance in terms of the diversity and coding gains. The analysis is accompanied by numerical evaluated results, clearly demonstrating the usefulness of the proposed theoretical framework.