Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInfo-Clustering: An Efficient Algorithm by Network Information Flow
113
0
0.0
(
0
)
Added by
Chung Chan
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Motivated by the fact that entities in a social network or biological system often interact by exchanging information, we propose an efficient info-clustering algorithm that can group entities into communities using a parametric max-flow algorithm. This is a meaningful special case of the info-clustering paradigm where the dependency structure is graphical and can be learned readily from data.
rate research
Read More
An agglomerative clustering of random variables is proposed, where clusters of random variables sharing the maximum amount of multivariate mutual information are merged successively to form larger clusters. Compared to the previous info-clustering algorithms, the agglomerative approach allows the computation to stop earlier when clusters of desired size and accuracy are obtained. An efficient algorithm is also derived based on the submodularity of entropy and the duality between the principal sequence of partitions and the principal sequence for submodular functions.
Modern image and video compression codes employ elaborate structures existing in such signals to encode them into few number of bits. Compressed sensing recovery algorithms on the other hand use such signals structures to recover them from few linear observations. Despite the steady progress in the field of compressed sensing, structures that are often used for signal recovery are still much simpler than those employed by state-of-the-art compression codes. The main goal of this paper is to bridge this gap through answering the following question: Can one employ a given compression code to build an efficient (polynomial time) compressed sensing recovery algorithm? In response to this question, the compression-based gradient descent (C-GD) algorithm is proposed. C-GD, which is a low-complexity iterative algorithm, is able to employ a generic compression code for compressed sensing and therefore elevates the scope of structures used in compressed sensing to those used by compression codes. The convergence performance of C-GD and its required number of measurements in terms of the rate-distortion performance of the compression code are theoretically analyzed. It is also shown that C-GD is robust to additive white Gaussian noise. Finally, the presented simulation results show that combining C-GD with commercial image compression codes such as JPEG2000 yields state-of-the-art performance in imaging applications.
We develop a theoretical framework for defining and identifying flows of information in computational systems. Here, a computational system is assumed to be a directed graph, with clocked nodes that send transmissions to each other along the edges of the graph at discrete points in time. We are interested in a definition that captures the dynamic flow of information about a specific message, and which guarantees an unbroken information path between appropriately defined inputs and outputs in the directed graph. Prior measures, including those based on Granger Causality and Directed Information, fail to provide clear assumptions and guarantees about when they correctly reflect information flow about a message. We take a systematic approach---iterating through candidate definitions and counterexamples---to arrive at a definition for information flow that is based on conditional mutual information, and which satisfies desirable properties, including the existence of information paths. Finally, we describe how information flow might be detected in a noiseless setting, and provide an algorithm to identify information paths on the time-unrolled graph of a computational system.
Cyclic redundancy check (CRC) codes combined with convolutional codes yield a powerful concatenated code that can be efficiently decoded using list decoding. To help design such systems, this paper presents an efficient algorithm for identifying the distance-spectrum-optimal (DSO) CRC polynomial for a given tail-biting convolutional code (TBCC) when the target undetected error rate (UER) is small. Lou et al. found that the DSO CRC design for a given zero-terminated convolutional code under low UER is equivalent to maximizing the undetected minimum distance (the minimum distance of the concatenated code). This paper applies the same principle to design the DSO CRC for a given TBCC under low target UER. Our algorithm is based on partitioning the tail-biting trellis into several disjoint sets of tail-biting paths that are closed under cyclic shifts. This paper shows that the tail-biting path in each set can be constructed by concatenating the irreducible error events (IEEs) and circularly shifting the resultant path. This motivates an efficient collection algorithm that aims at gathering IEEs, and a search algorithm that reconstructs the full list of error events with bounded distance of interest, which can be used to find the DSO CRC. Simulation results show that DSO CRCs can significantly outperform suboptimal CRCs in the low UER regime.
We consider the problem of sparse signal recovery from 1-bit measurements. Due to the noise present in the acquisition and transmission process, some quantized bits may be flipped to their opposite states. These sign flips may result in severe performance degradation. In this study, a novel algorithm, termed HISTORY, is proposed. It consists of Hamming support detection and coefficients recovery. The HISTORY algorithm has high recovery accuracy and is robust to strong measurement noise. Numerical results are provided to demonstrate the effectiveness and superiority of the proposed algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
