OpenRaiser/Intern-Atlas huggingface dataset:
Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing
Venue: arXiv cs.IT 2010
Year: 2010

We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. Relaxed BP uses a Gaussian approximation in standard BP to obtain significant computational savings for dense measurement matrices. The main contribution of this paper is to extend the relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that relaxed BP has an identical asymptotic large sparse limit behavior as standard BP, as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.
Classifying Application Phases in Asymmetric Chip Multiprocessors
Venue: arXiv cs.DC 2010
Year: 2010

In present study, in order to improve the performance and reduce the amount of power which is dissipated in heterogeneous multicore processors, the ability of detecting the program execution phases is investigated. The programs execution intervals have been classified in different phases based on their throughput and the utilization of the cores. The results of implementing the phase detection technique are investigated on a single core processor and also on a multicore processor. To minimize the profiling overhead, an algorithm for the dynamic adjustment of the profiling intervals is presented. It is based on the behavior of the program and reduces the profiling overhead more than three fold. The results are obtained from executing multiprocessor benchmarks on a given processor. In order to show the program phases clearly, throughput and utilization of execution intervals are presented on a scatter plot. The results are presented for both fixed and variable intervals.
Sinusoidal Frequency Doublers Circuit With Low Voltage 1.5 Volt CMOS Inverter
Venue: arXiv cs.OH 2010
Year: 2010

This paper is present sinusoidal frequency doublers circuit with low voltage 1.5 volt CMOS inverter. Main structure of circuit has three parts that is CMOS inverter circuit, differential amplifier circuit, and square root circuit. This circuit has designed to receive input voltage and give output voltage use few MOS transistor, easy to understand, non complex of circuit, high precision, low error and low power. The Simulation of circuit has MOS transistor functional in active and saturation period. PSpice programmed has used to confirmation of testing and simulation.
Network Capacity Region of Multi-Queue Multi-Server Queueing System with Time Varying Connectivities
Venue: arXiv cs.IT 2010
Year: 2010

Network capacity region of multi-queue multi-server queueing system with random ON-OFF connectivities and stationary arrival processes is derived in this paper. Specifically, the necessary and sufficient conditions for the stability of the system are derived under general arrival processes with finite first and second moments. In the case of stationary arrival processes, these conditions establish the network capacity region of the system. It is also shown that AS/LCQ (Any Server/Longest Connected Queue) policy stabilizes the system when it is stabilizable. Furthermore, an upper bound for the average queue occupancy is derived for this policy.
The Application of Mamdani Fuzzy Model for Auto Zoom Function of a Digital Camera
Venue: arXiv cs.AI 2010
Year: 2010

Mamdani Fuzzy Model is an important technique in Computational Intelligence (CI) study. This paper presents an implementation of a supervised learning method based on membership function training in the context of Mamdani fuzzy models. Specifically, auto zoom function of a digital camera is modelled using Mamdani technique. The performance of control method is verified through a series of simulation and numerical results are provided as illustrations.
Comparative Evaluation and Analysis of IAX and RSW
Venue: arXiv cs.NI 2010
Year: 2010

Voice over IP (VoIP) is a technology to transport media over IP networks such as the Internet. VoIP has the capability of connecting people over packet switched networks instead of traditional circuit switched networks. Recently, the InterAsterisk Exchange Protocol (IAX) has emerged as a new VoIP which is gaining popularity among VoIP products. IAX is known for its simplicity, NAT friendliness, efficiency, and robustness. More recently, the Real time Switching (RSW) control criterion has emerged as a multimedia conferencing protocol. In this paper, we made a comparative evaluation and analysis of IAX and RSW using Mean Opinion Score rating (MOS) and found that they both perform well under different network packet delays in ms.
Circuit partitions and #P-complete products of inner products
Venue: arXiv cs.CC 2010
Year: 2010

We present a simple, natural #P-complete problem. Let G be a directed graph, and let k be a positive integer. We define q(G;k) as follows. At each vertex v, we place a k-dimensional complex vector x_v. We take the product, over all edges (u,v), of the inner product <x_u,x_v>. Finally, q(G;k) is the expectation of this product, where the x_v are chosen uniformly and independently from all vectors of norm 1 (or, alternately, from the Gaussian distribution). We show that q(G;k) is proportional to G's cycle partition polynomial, and therefore that it is #P-complete for any k>1.
Wiretap Channel with Causal State Information
Venue: arXiv cs.IT 2010
Year: 2010

A lower bound on the secrecy capacity of the wiretap channel with state information available causally at both the encoder and decoder is established. The lower bound is shown to be strictly larger than that for the noncausal case by Liu and Chen. Achievability is proved using block Markov coding, Shannon strategy, and key generation from common state information. The state sequence available at the end of each block is used to generate a key, which is used to enhance the transmission rate of the confidential message in the following block. An upper bound on the secrecy capacity when the state is available noncausally at the encoder and decoder is established and is shown to coincide with the lower bound for several classes of wiretap channels with state.
Network-Level Cooperative Protocols for Wireless Multicasting: Stable Throughput Analysis and Use of Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we investigate the impact of network coding at the relay node on the stable throughput rate in multicasting cooperative wireless networks. The proposed protocol adopts Network-level cooperation in contrast to the traditional physical layer cooperative protocols and in addition uses random linear network coding at the relay node. The traffic is assumed to be bursty and the relay node forwards its packets during the periods of source silence which allows better utilization for channel resources. Our results show that cooperation will lead to higher stable throughput rates than conventional retransmission policies and that the use of random linear network coding at the relay can further increase the stable throughput with increasing Network Coding field size or number of packets over which encoding is performed.
A Hybrid RTS-BP Algorithm for Improved Detection of Large-MIMO M-QAM Signals
Venue: arXiv cs.IT 2010
Year: 2010

Low-complexity near-optimal detection of large-MIMO signals has attracted recent research. Recently, we proposed a local neighborhood search algorithm, namely `reactive tabu search' (RTS) algorithm, as well as a factor-graph based `belief propagation' (BP) algorithm for low-complexity large-MIMO detection. The motivation for the present work arises from the following two observations on the above two algorithms: $i)$ RTS works for general M-QAM. Although RTS was shown to achieve close to optimal performance for 4-QAM in large dimensions, significant performance improvement was still possible for higher-order QAM (e.g., 16- and 64-QAM). ii) BP also was shown to achieve near-optimal performance for large dimensions, but only for $\{\pm 1\}$ alphabet. In this paper, we improve the large-MIMO detection performance of higher-order QAM signals by using a hybrid algorithm that employs RTS and BP. In particular, motivated by the observation that when a detection error occurs at the RTS output, the least significant bits (LSB) of the symbols are mostly in error, we propose to first reconstruct and cancel the interference due to bits other than LSBs at the RTS output and feed the interference cancelled received signal to the BP algorithm to improve the reliability of the LSBs. The output of the BP is then fed back to RTS for the next iteration. Our simulation results show that in a 32 x 32 V-BLAST system, the proposed RTS-BP algorithm performs better than RTS by about 3.5 dB at $10^{-3}$ uncoded BER and by about 2.5 dB at $3\times 10^{-4}$ rate-3/4 turbo coded BER with 64-QAM at the same order of complexity as RTS. We also illustrate the performance of large-MIMO detection in frequency-selective fading channels.
Towards Improving the Mental Model of Software Developers through Cartographic Visualization
Venue: arXiv cs.SE 2010
Year: 2010

Software is intangible and knowledge about software systems is typically tacit. The mental model of software developers is thus an important factor in software engineering. It is our vision that developers should be able to refer to code as being "up in the north", "over in the west", or "down-under in the south". We want to provide developers, and everyone else involved in software development, with a *shared*, spatial and stable mental model of their software project. We aim to reinforce this by embedding a cartographic visualization in the IDE (Integrated Development Environment). The visualization is always visible in the bottom-left, similar to the GPS navigation device for car drivers. For each development task, related information is displayed on the map. In this paper we present CODEMAP, an eclipse plug-in, and report on preliminary results from an ongoing user study with professional developers and students.
A Little More, a Lot Better: Improving Path Quality by a Simple Path Merging Algorithm
Venue: arXiv cs.RO 2010
Year: 2010

Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths (with respect to quality measures such as path length, clearance, smoothness or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm for merging an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain sub-paths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed for comparing and clustering multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.
Check Reliability Based Bit-Flipping Decoding Algorithms for LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

We introduce new reliability definitions for bit and check nodes. Maximizing global reliability, which is the sum reliability of all bit nodes, is shown to be equivalent to minimizing a decoding metric which is closely related to the maximum likelihood decoding metric. We then propose novel bit-flipping (BF) decoding algorithms that take into account the check node reliability. Both hard-decision (HD) and soft-decision (SD) versions are considered. The former performs better than the conventional BF algorithm and, in most cases, suffers less than 1 dB performance loss when compared with some well known SD BF decoders. For one particular code it even outperforms those SD BF decoders. The performance of the SD version is superior to that of SD BF decoders and is comparable to or even better than that of the sum-product algorithm (SPA). The latter is achieved with a complexity much less than that required by the SPA.
Concatenated Polar Codes
Venue: arXiv cs.IT 2010
Year: 2010

Polar codes have attracted much recent attention as the first codes with low computational complexity that provably achieve optimal rate-regions for a large class of information-theoretic problems. One significant drawback, however, is that for current constructions the probability of error decays sub-exponentially in the block-length (more detailed designs improve the probability of error at the cost of significantly increased computational complexity \cite{KorUS09}). In this work we show how the the classical idea of code concatenation -- using "short" polar codes as inner codes and a "high-rate" Reed-Solomon code as the outer code -- results in substantially improved performance. In particular, code concatenation with a careful choice of parameters boosts the rate of decay of the probability of error to almost exponential in the block-length with essentially no loss in computational complexity. We demonstrate such performance improvements for three sets of information-theoretic problems -- a classical point-to-point channel coding problem, a class of multiple-input multiple output channel coding problems, and some network source coding problems.
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs
Venue: arXiv cs.LO 2010
Year: 2010

The question of whether there is a logic that captures polynomial time was formulated by Yuri Gurevich in 1988. It is still wide open and regarded as one of the main open problems in finite model theory and database theory. Partial results have been obtained for specific classes of structures. In particular, it is known that fixed-point logic with counting captures polynomial time on all classes of graphs with excluded minors. The introductory part of this paper is a short survey of the state-of-the-art in the quest for a logic capturing polynomial time. The main part of the paper is concerned with classes of graphs defined by excluding induced subgraphs. Two of the most fundamental such classes are the class of chordal graphs and the class of line graphs. We prove that capturing polynomial time on either of these classes is as hard as capturing it on the class of all graphs. In particular, this implies that fixed-point logic with counting does not capture polynomial time on these classes. Then we prove that fixed-point logic with counting does capture polynomial time on the class of all graphs that are both chordal and line graphs.
Approximating Matrix p-norms
Venue: arXiv cs.DS 2010
Year: 2010

We consider the problem of computing the q->p norm of a matrix A, which is defined for p,q \ge 1, as |A|_{q->p} = max_{x !=0 } |Ax|_p / |x|_q. This is in general a non-convex optimization problem, and is a natural generalization of the well-studied question of computing singular values (this corresponds to p=q=2). Different settings of parameters give rise to a variety of known interesting problems (such as the Grothendieck problem when p=1 and q=\infty). However, very little is understood about the approximability of the problem for different values of p,q. Our first result is an efficient algorithm for computing the q->p norm of matrices with non-negative entries, when q \ge p \ge 1. The algorithm we analyze is based on a natural fixed point iteration, which can be seen as an analog of power iteration for computing eigenvalues. We then present an application of our techniques to the problem of constructing a scheme for oblivious routing in the l_p norm. This makes constructive a recent existential result of Englert and Räcke [ER] on O(log n)-competitive oblivious routing schemes (which they make constructive only for p=2). On the other hand, when we do not have any restrictions on the entries (such as non-negativity), we prove that the problem is NP-hard to approximate to any constant factor, for 2 < p \le q, and p \le q < 2 (these are precisely the ranges of p,q with p\le q, where constant factor approximations are not known). In this range, our techniques also show that if NP does not have quasi-polynomial time algorithms, the q->p cannot be approximated to a factor 2^{(log n)^{1-eps}}, for any \eps>0.
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
Venue: arXiv cs.DS 2010
Year: 2010

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n^(1/3-epsilon) for some specific epsilon > 0 (estimated at around 1/60). We present an algorithm that for every epsilon > 0 approximates the Densest k-Subgraph problem within a ratio of n^(1/4+epsilon) in time n^O(1/epsilon). In particular, our algorithm achieves an approximation ratio of O(n^1/4) in time n^O(log n). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from graphs with planted dense subgraphs. The approximation ratio we achieve for the general case matches the distinguishing ratio we obtain for this planted problem. At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. Our algorithm is based on the following principle. We say that a graph G(V,E) has log-density alpha if its average degree is Theta(|V|^alpha). The algorithmic core of our result is a family of algorithms that output k-subgraphs of nontrivial density whenever the log-density of the densest k-subgraph is larger than the log-density of the host graph.
Source Polarization
Venue: arXiv cs.IT 2010
Year: 2010

The notion of source polarization is introduced and investigated. This complements the earlier work on channel polarization. An application to Slepian-Wolf coding is also considered. The paper is restricted to the case of binary alphabets. Extension of results to non-binary alphabets is discussed briefly.
On the Capacity Achieving Covariance Matrix for Frequency Selective MIMO Channels Using the Asymptotic Approach
Venue: arXiv cs.IT 2010
Year: 2010

In this contribution, an algorithm for evaluating the capacity-achieving input covariance matrices for frequency selective Rayleigh MIMO channels is proposed. In contrast with the flat fading Rayleigh cases, no closed-form expressions for the eigenvectors of the optimum input covariance matrix are available. Classically, both the eigenvectors and eigenvalues are computed numerically and the corresponding optimization algorithms remain computationally very demanding. In this paper, it is proposed to optimize (w.r.t. the input covariance matrix) a large system approximation of the average mutual information derived by Moustakas and Simon. An algorithm based on an iterative water filling scheme is proposed, and its convergence is studied. Numerical simulation results show that, even for a moderate number of transmit and receive antennas, the new approach provides the same results as direct maximization approaches of the average mutual information.
Gaze and Gestures in Telepresence: multimodality, embodiment, and roles of collaboration
Venue: arXiv cs.HC 2010
Year: 2010

This paper proposes a controlled experiment to further investigate the usefulness of gaze awareness and gesture recognition in the support of collaborative work at a distance. We propose to redesign experiments conducted several years ago with more recent technology that would: a) enable to better study of the integration of communication modalities, b) allow users to freely move while collaborating at a distance and c) avoid asymmetries of communication between collaborators.
Optimal Reverse Carpooling Over Wireless Networks - A Distributed Optimization Approach
Venue: arXiv cs.NI 2010
Year: 2010

We focus on a particular form of network coding, reverse carpooling, in a wireless network where the potentially coded transmitted messages are to be decoded immediately upon reception. The network is fixed and known, and the system performance is measured in terms of the number of wireless broadcasts required to meet multiple unicast demands. Motivated by the structure of the coding scheme, we formulate the problem as a linear program by introducing a flow variable for each triple of connected nodes. This allows us to have a formulation polynomial in the number of nodes. Using dual decomposition and projected subgradient method, we present a decentralized algorithm to obtain optimal routing schemes in presence of coding opportunities. We show that the primal sub-problem can be expressed as a shortest path problem on an \emph{edge-graph}, and the proposed algorithm requires each node to exchange information only with its neighbors.
Weak ties: Subtle role of information diffusion in online social networks
Venue: arXiv cs.SI 2010
Year: 2010

As a social media, online social networks play a vital role in the social information diffusion. However, due to its unique complexity, the mechanism of the diffusion in online social networks is different from the ones in other types of networks and remains unclear to us. Meanwhile, few works have been done to reveal the coupled dynamics of both the structure and the diffusion of online social networks. To this end, in this paper, we propose a model to investigate how the structure is coupled with the diffusion in online social networks from the view of weak ties. Through numerical experiments on large-scale online social networks, we find that in contrast to some previous research results, selecting weak ties preferentially to republish cannot make the information diffuse quickly, while random selection can achieve this goal. However, when we remove the weak ties gradually, the coverage of the information will drop sharply even in the case of random selection. We also give a reasonable explanation for this by extra analysis and experiments. Finally, we conclude that weak ties play a subtle role in the information diffusion in online social networks. On one hand, they act as bridges to connect isolated local communities together and break through the local trapping of the information. On the other hand, selecting them as preferential paths to republish cannot help the information spread further in the network. As a result, weak ties might be of use in the control of the virus spread and the private information diffusion in real-world applications.