OpenRaiser/Intern-Atlas huggingface dataset:
Linear Programming based Converses for Finite Blocklength Lossy Joint Source-Channel Coding
Venue: arXiv cs.IT 2017
Year: 2017

A linear programming (LP) based framework is presented for obtaining converses for finite blocklength lossy joint source-channel coding problems. The framework applies for any loss criterion, generalizes certain previously known converses, and also extends to multi-terminal settings. The finite blocklength problem is posed equivalently as a nonconvex optimization problem and using a lift-and-project-like method, a close but tractable LP relaxation of this problem is derived. Lower bounds on the original problem are obtained by the construction of feasible points for the dual of the LP relaxation. A particular application of this approach leads to new converses which recover and improve on the converses of Kostina and Verdu for finite blocklength lossy joint source-channel coding and lossy source coding. For finite blocklength channel coding, the LP relaxation recovers the converse of Polyanskiy, Poor and Verdu and leads to a new improvement on the converse of Wolfowitz, showing thereby that our LP relaxation is asymptotically tight with increasing blocklengths for channel coding, lossless source coding and joint source-channel coding with the excess distortion probability as the loss criterion. Using a duality based argument, a new converse is derived for finite blocklength joint source-channel coding for a class of source-channel pairs. Employing this converse, the LP relaxation is also shown to be tight for all blocklengths for the minimization of the expected average symbol-wise Hamming distortion of a $q$-ary uniform source over a $q$-ary symmetric memoryless channel for any $q \in N$. The optimization formulation and the lift-and-project method are extended to networked settings and demonstrated by obtaining an improvement on a converse of Zhou et al. for the successive refinement problem for successively refinable source-distortion measure triplets.
Inapproximability Results for Approximate Nash Equilibria
Venue: arXiv cs.GT 2017
Year: 2017

We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem $ε$-NE $δ$-SW: find an $ε$-approximate Nash equilibrium ($ε$-NE) that is within $δ$ of the best social welfare achievable by an $ε$-NE. Our main result is that, if the exponential-time hypothesis (ETH) is true, then solving $\left(\frac{1}{8} - \mathrm{O}(δ)\right)$-NE $\mathrm{O}(δ)$-SW for an $n\times n$ bimatrix game requires $n^{\mathrm{\widetilde Ω}(\log n)}$ time. Building on this result, we show similar conditional running time lower bounds on a number of decision problems for approximate Nash equilibria that do not involve social welfare, including maximizing or minimizing a certain player's payoff, or finding approximate equilibria contained in a given pair of supports. We show quasi-polynomial lower bounds for these problems assuming that ETH holds, where these lower bounds apply to $ε$-Nash equilibria for all $ε< \frac{1}{8}$. The hardness of these other decision problems has so far only been studied in the context of exact equilibria.
All Your Bulbs Are Belong to Us: Investigating the Current State of Security in Connected Lighting Systems
Venue: arXiv cs.CR 2017
Year: 2017

ZigBee Light Link (ZLL) is the low-power mesh network standard used by connected lighting systems, such as Philips Hue, Osram Lightify, and GE Link. These lighting systems are intended for residential use but also deployed in hotels, restaurants, and industrial buildings. In this paper, we investigate the current state of security in ZLL-based connected lighting systems. We extend the scope of known attacks by describing novel attack procedures to show that the ZLL standard is insecure by design. Using our penetration testing framework, we are able to take full control over all three systems mentioned above. Besides novel attack procedures, we also extend the intended wireless range of max. 2 meters for configuring a ZLL device to over 30 meters, thus making ZLL-based systems susceptible to war driving. We conclude with a discussion about the security needs of connected lighting systems and derive several lessons for Internet of Things security that can be learned from the insecure design of ZLL-based connected lighting systems.
Self-paced Learning for Weakly Supervised Evidence Discovery in Multimedia Event Search
Venue: arXiv cs.CV 2017
Year: 2017

Multimedia event detection has been receiving increasing attention in recent years. Besides recognizing an event, the discovery of evidences (which is refered to as "recounting") is also crucial for user to better understand the searching result. Due to the difficulty of evidence annotation, only limited supervision of event labels are available for training a recounting model. To deal with the problem, we propose a weakly supervised evidence discovery method based on self-paced learning framework, which follows a learning process from easy "evidences" to gradually more complex ones, and simultaneously exploit more and more positive evidence samples from numerous weakly annotated video segments. Moreover, to evaluate our method quantitatively, we also propose two metrics, \textit{PctOverlap} and \textit{F1-score}, for measuring the performance of evidence localization specifically. The experiments are conducted on a subset of TRECVID MED dataset and demonstrate the promising results obtained by our method.
Sub-Nyquist SAR via Fourier Domain Range Doppler Processing
Venue: arXiv cs.IT 2017
Year: 2017

Conventional Synthetic Aperture Radar (SAR) systems are limited in their ability to satisfy the increasing requirement for improved spatial resolution and wider coverage. The demand for high resolution requires high sampling rates, while coverage is limited by the pulse repetition frequency. Consequently, sampling rate reduction is of high practical value in SAR imaging. In this paper, we introduce a new algorithm, equivalent to the well-known Range-Doppler method, to process SAR data using the Fourier series coefficients of the raw signals. We then demonstrate how to exploit the algorithm features to reduce sampling rate in both range and azimuth axes and process the signals at sub-Nyquist rates, by using compressed sensing (CS) tools. In particular, we demonstrate recovery of an image using only a portion of the received signal's bandwidth and also while dropping a large percentage of the transmitted pulses. The complementary pulses may be used to capture other scenes within the same coherent processing interval. In addition, we propose exploiting the ability to reconstruct the image from narrow bands in order to dynamically adapt the transmitted waveform energy to vacant spectral bands, paving the way to cognitive SAR. The proposed recovery algorithms form a new CS-SAR imaging method that can be applied to high-resolution SAR data acquired at sub-Nyquist rates in range and azimuth. The performance of our method is assessed using simulated and real data sets. Finally, our approach is implemented in hardware using a previously suggested Xampling radar prototype.
Power Data Classification: A Hybrid of a Novel Local Time Warping and LSTM
Venue: arXiv cs.NE 2017
Year: 2017

In this paper, for the purpose of data centre energy consumption monitoring and analysis, we propose to detect the running programs in a server by classifying the observed power consumption series. Time series classification problem has been extensively studied with various distance measurements developed; also recently the deep learning based sequence models have been proved to be promising. In this paper, we propose a novel distance measurement and build a time series classification algorithm hybridizing nearest neighbour and long short term memory (LSTM) neural network. More specifically, first we propose a new distance measurement termed as Local Time Warping (LTW), which utilizes a user-specified set for local warping, and is designed to be non-commutative and non-dynamic programming. Second we hybridize the 1NN-LTW and LSTM together. In particular, we combine the prediction probability vector of 1NN-LTW and LSTM to determine the label of the test cases. Finally, using the power consumption data from a real data center, we show that the proposed LTW can improve the classification accuracy of DTW from about 84% to 90%. Our experimental results prove that the proposed LTW is competitive on our data set compared with existed DTW variants and its non-commutative feature is indeed beneficial. We also test a linear version of LTW and it can significantly outperform existed linear runtime lower bound methods like LB_Keogh. Furthermore, with the hybrid algorithm, for the power series classification task we achieve an accuracy up to about 93%. Our research can inspire more studies on time series distance measurement and the hybrid of the deep learning models with other traditional models.
Design of Efficient Convolutional Layers using Single Intra-channel Convolution, Topological Subdivisioning and Spatial "Bottleneck" Structure
Venue: arXiv cs.CV 2017
Year: 2017

Deep convolutional neural networks achieve remarkable visual recognition performance, at the cost of high computational complexity. In this paper, we have a new design of efficient convolutional layers based on three schemes. The 3D convolution operation in a convolutional layer can be considered as performing spatial convolution in each channel and linear projection across channels simultaneously. By unravelling them and arranging the spatial convolution sequentially, the proposed layer is composed of a single intra-channel convolution, of which the computation is negligible, and a linear channel projection. A topological subdivisioning is adopted to reduce the connection between the input channels and output channels. Additionally, we also introduce a spatial "bottleneck" structure that utilizes a convolution-projection-deconvolution pipeline to take advantage of the correlation between adjacent pixels in the input. Our experiments demonstrate that the proposed layers remarkably outperform the standard convolutional layers with regard to accuracy/complexity ratio. Our models achieve similar accuracy to VGG, ResNet-50, ResNet-101 while requiring 42, 4.5, 6.5 times less computation respectively.
Live Prefetching for Mobile Computation Offloading
Venue: arXiv cs.IT 2017
Year: 2017

The conventional designs of mobile computation offloading fetch user-specific data to the cloud prior to computing, called offline prefetching. However, this approach can potentially result in excessive fetching of large volumes of data and cause heavy loads on radio-access networks. To solve this problem, the novel technique of live prefetching is proposed in this paper that seamlessly integrates the task-level computation prediction and prefetching within the cloud-computing process of a large program with numerous tasks. The technique avoids excessive fetching but retains the feature of leveraging prediction to reduce the program runtime and mobile transmission energy. By modeling the tasks in an offloaded program as a stochastic sequence, stochastic optimization is applied to design fetching policies to minimize mobile energy consumption under a deadline constraint. The policies enable real-time control of the prefetched-data sizes of candidates for future tasks. For slow fading, the optimal policy is derived and shown to have a threshold-based structure, selecting candidate tasks for prefetching and controlling their prefetched data based on their likelihoods. The result is extended to design close-to-optimal prefetching policies to fast fading channels. Compared with fetching without prediction, live prefetching is shown theoretically to always achieve reduction on mobile energy consumption.
IM2CAD
Venue: arXiv cs.CV 2017
Year: 2017

Given a single photo of a room and a large database of furniture CAD models, our goal is to reconstruct a scene that is as similar as possible to the scene depicted in the photograph, and composed of objects drawn from the database. We present a completely automatic system to address this IM2CAD problem that produces high quality results on challenging imagery from interior home design and remodeling websites. Our approach iteratively optimizes the placement and scale of objects in the room to best match scene renderings to the input photo, using image comparison metrics trained via deep convolutional neural nets. By operating jointly on the full scene at once, we account for inter-object occlusions. We also show the applicability of our method in standard scene understanding benchmarks where we obtain significant improvement.
Haploid-Diploid Evolutionary Algorithms
Venue: arXiv cs.NE 2017
Year: 2017

This paper uses the recent idea that the fundamental haploid-diploid lifecycle of eukaryotic organisms implements a rudimentary form of learning within evolution. A general approach for evolutionary computation is here derived that differs from all previous known work using diploid representations. The primary role of recombination is also changed from that previously considered in both natural and artificial evolution under the new view. Using well-known abstract tuneable models it is shown that varying fitness landscape ruggedness varies the benefit of the new approach.
OFDM Without CP in Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

We study the possibility of removing the cyclic prefix (CP) overhead from orthogonal frequency division multiplexing (OFDM) in massive multiple-input multiple-output (MIMO) systems. We consider the uplink transmission while our results are applicable to the downlink as well. The absence of CP increases the spectral efficiency in expense of intersymbol interference (ISI) and intercarrier interference (ICI). It is known that in massive MIMO, the effects of uncorrelated noise and multiuser interference vanish as the number of base station (BS) antennas tends to infinity. To investigate if the channel distortions in the absence of CP fade away, we study the performance of the standard maximum ratio combining (MRC) receiver. Our analysis reveals that in this receiver, there always remains some residual interference leading to saturation of signal-to-interference-plus-noise ratio (SINR). To resolve this problem, we propose to use the time reversal (TR) technique. Moreover, in order to further reduce the multiuser interference, we propose a zero-forcing equalization to be deployed after the TR combining. We compare the achievable rate of the proposed system with that of the conventional CP-OFDM. We show that in realistic channels, a higher spectral efficiency is achieved by removing the CP from OFDM, while reducing the computational complexity.
Effects of Base-Station Spatial Interdependence on Interference Correlation and Network Performance
Venue: arXiv cs.IT 2017
Year: 2017

The spatial-and-temporal correlation of interference has been well studied in Poisson networks where the interfering base stations (BSs) are independent of each other. However, there exists spatial interdependence including attraction and repulsion among the BSs in practical wireless networks, affecting the interference distribution and hence the network performance. In view of this, by modeling the network as a Poisson clustered process, we quantify the effects of spatial interdependence among BSs on the interference correlation and analytically prove that BS clustering increases the level of interference correlation. In particular, it is shown that the level increases as the attraction between the BSs increases. Furthermore, we study the effects of spatial interdependence among BSs on network performance with a retransmission scheme via considering heterogeneous cellular networks in which small-cell BSs exhibit a clustered topology in practice. It is shown that the interference correlation degrades the network performance and the degradation increases as the attraction between BSs increases. Finally, a correlation-aware retransmission scheme is proposed to improve the network performance by taking advantage of the interference correlation and avoiding the blind retransmissions.
On Preambles With Low Out of Band Radiation for Channel Estimation
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we investigate preamble designs for channel estimation, that jointly address the estimation efficiency in terms of MSE of the channel estimates, and the OOB radiation of the transmit preambles. We provide two novel design techniques, based on a convex optimization problem, to obtain optimal preambles for a single carrier and provide a juxtaposition based method to extend their application to multi-carrier systems. The obtained preambles are shown to have 10 dB to 35 dB lower OOB radiation than the existing preamble based estimation techniques. We also show the fundamental trade-off between the estimation efficiency and the OOB radiation and highlight that the improved OOB performance comes at a cost of increased estimation error. Finally, as a case study, the estimated channel values are used in equalization of a MIMO GFDM system that is aimed for transmit diversity.
Arbitrarily regularizable graphs
Venue: arXiv cs.SI 2017
Year: 2017

A graph is regularizable if it is possible to assign weights to its edges so that all nodes have the same degree. Weights can be positive, nonnegative or arbitrary as soon as the regularization degree is not null. Positive and nonnegative regularizable graphs have been thoroughly investigated in the literature. In this work, we propose and study arbitrarily regularizable graphs. In particular, we investigate necessary and sufficient regularization conditions on the topology of the graph and of the corresponding adjacency matrix. Moreover, we study the computational complexity of the regularization problem and characterize it as a linear programming model.
Dynamic Multi-Objectives Optimization with a Changing Number of Objectives
Venue: arXiv cs.NE 2017
Year: 2017

Existing studies on dynamic multi-objective optimization focus on problems with time-dependent objective functions, while the ones with a changing number of objectives have rarely been considered in the literature. Instead of changing the shape or position of the Pareto-optimal front/set when having time-dependent objective functions, increasing or decreasing the number of objectives usually leads to the expansion or contraction of the dimension of the Pareto-optimal front/set manifold. Unfortunately, most existing dynamic handling techniques can hardly be adapted to this type of dynamics. In this paper, we report our attempt toward tackling the dynamic multi-objective optimization problems with a changing number of objectives. We implement a new two-archive evolutionary algorithm which maintains two co-evolving populations simultaneously. In particular, these two populations are complementary to each other: one concerns more about the convergence while the other concerns more about the diversity. The compositions of these two populations are adaptively reconstructed once the environment changes. In addition, these two populations interact with each other via a mating selection mechanism. Comprehensive experiments are conducted on various benchmark problems with a time-dependent number of objectives. Empirical results fully demonstrate the effectiveness of our proposed algorithm.
Unsupervised, Efficient and Semantic Expertise Retrieval
Venue: arXiv cs.IR 2017
Year: 2017

We introduce an unsupervised discriminative model for the task of retrieving experts in online document collections. We exclusively employ textual evidence and avoid explicit feature engineering by learning distributed word representations in an unsupervised way. We compare our model to state-of-the-art unsupervised statistical vector space and probabilistic generative approaches. Our proposed log-linear model achieves the retrieval performance levels of state-of-the-art document-centric methods with the low inference cost of so-called profile-centric approaches. It yields a statistically significant improved ranking over vector space and generative models in most cases, matching the performance of supervised methods on various benchmarks. That is, by using solely text we can do as well as methods that work with external evidence and/or relevance feedback. A contrastive analysis of rankings produced by discriminative and generative approaches shows that they have complementary strengths due to the ability of the unsupervised discriminative model to perform semantic matching.
Study on the Idle Mode Capability with LoS and NLoS Transmissions
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we study the impact of the base station (BS) idle mode capability (IMC) on the network performance in dense small cell networks (SCNs). Different from existing works, we consider a sophisticated path loss model incorporating both line-of-sight (LoS) and non-line-of-sight (NLoS) transmissions. Analytical results are obtained for the coverage probability and the area spectral efficiency (ASE) performance for SCNs with IMCs at the BSs. The upper bound, the lower bound and the approximate expression of the activated BS density are also derived. The performance impact of the IMC is shown to be significant. As the BS density surpasses the UE density, thus creating a surplus of BSs, the coverage probability will continuously increase toward one. For the practical regime of the BS density, the results derived from our analysis are distinctively different from existing results, and thus shed new light on the deployment and the operation of future dense SCNs.
Absolute Pose Estimation from Line Correspondences using Direct Linear Transformation
Venue: arXiv cs.CV 2017
Year: 2017

This work is concerned with camera pose estimation from correspondences of 3D/2D lines, i. e. with the Perspective-n-Line (PnL) problem. We focus on large line sets, which can be efficiently solved by methods using linear formulation of PnL. We propose a novel method "DLT-Combined-Lines" based on the Direct Linear Transformation (DLT) algorithm, which benefits from a new combination of two existing DLT methods for pose estimation. The method represents 2D structure by lines, and 3D structure by both points and lines. The redundant 3D information reduces the minimum required line correspondences to 5. A cornerstone of the method is a combined projection matri xestimated by the DLT algorithm. It contains multiple estimates of camera rotation and translation, which can be recovered after enforcing constraints of the matrix. Multiplicity of the estimates is exploited to improve the accuracy of the proposed method. For large line sets (10 and more), the method is comparable to the state-of-theart in accuracy of orientation estimation. It achieves state-of-the-art accuracy in estimation of camera position and it yields the smallest reprojection error under strong image noise. The method achieves top-3 results on real world data. The proposed method is also highly computationally effective, estimating the pose of 1000 lines in 12 ms on a desktop computer.