An approximate sparse recovery system in l_1 norm makes a small number of measurements of a noisy vector with at most k large entries and recovers those heavy hitters approximately. Formally, it consists of parameters...
详细信息
ISBN:
(纸本)9781611972108
An approximate sparse recovery system in l_1 norm makes a small number of measurements of a noisy vector with at most k large entries and recovers those heavy hitters approximately. Formally, it consists of parameters N, k, ε, an m-by-N measurement matrix, φ, and a decoding algorithm, D. Given a vector, x, where x_k denotes the optimal k-term approximation to x, the system approximates x by {top}x = D(φx), which must satisfy ‖x{top}^ - x‖_1 ≤ (1 + ε) ‖x - x_k‖_1. Among the goals in designing such systems are minimizing the number m of measurements and the runtime of the decoding algorithm, D. We consider the "forall" model, in which a single matrix φ, possibly "constructed" non-explicitly using the probabilistic method, is used for all signals x.
A novel counter architecture, called Counter Braids, has recently been proposed for per-flow counting on high-speed links. Counter Braids has a layered structure and compresses the flow sizes as it counts. It has been...
详细信息
ISBN:
(纸本)9781424429257
A novel counter architecture, called Counter Braids, has recently been proposed for per-flow counting on high-speed links. Counter Braids has a layered structure and compresses the flow sizes as it counts. It has been shown that with a Maximum Likelihood (ML) decoding algorithm, the number of bits needed to store the size of a flow matches the entropy lower bound. As ML decoding is too complex to implement, an efficient message passing decoding algorithm has been proposed for practical purposes. The layers of Counter Braids are decoded sequentially, from the most significant to the least significant bits. In each layer, the message passing decoder solves a sparse signal recovery problem. In this paper we analyze the threshold dimensionality reduction rate (d-rate) of the message passing algorithm, and prove that it is correctly predicted by density evolution. Given a signal in R_+~n with TIE non-vanishing entries, we prove that one layer of Counter Braids can reduce its dimensionality by a factor 2.08·εlog(l/ε) + O(ε). This essentially matches the rate for sparse signal recovery via L_1 minimization, while keeping the overall complexity linear in n.
In the area of machine translation (MT) system combination, previous work on generating input hypotheses has focused on varying a core aspect of the MT system, such as the decoding algorithm or alignment algorithm. In...
详细信息
ISBN:
(纸本)9781937284206
In the area of machine translation (MT) system combination, previous work on generating input hypotheses has focused on varying a core aspect of the MT system, such as the decoding algorithm or alignment algorithm. In this paper, we propose a new method for generating diverse hypotheses from a single MT system using traits. These traits are simple properties of the MT output such as "average output length" and "average rule length." Our method is designed to select hypotheses which vary in trait value but do not significantly degrade in BLEU score. These hypotheses can be combined using standard system combination techniques to produce a 1.2-1.5 BLEU gain on the Arabic-English NIST MT06/MT08 translation task.
We present a new approach of the decoding algorithm for Gabidulin Codes. In the same way as efficient erasure decoding for Generalized Reed Solomon codes by using the structure of the inverse of the VanderMonde matric...
详细信息
Turbo (iterative) decoding can be implemented with a large family of soft- input soft-output (SISO) algorithms, including suboptimal but practical algorithms such as the soft- output Viterbi algorithm (SOVA) and max-l...
详细信息
Turbo (iterative) decoding can be implemented with a large family of soft- input soft-output (SISO) algorithms, including suboptimal but practical algorithms such as the soft- output Viterbi algorithm (SOVA) and max-log-MAP algorithm. The performance with these practical algorithms can be improved with simple scaling factor methods. However, their theoretical analysis was mainly based on the relaxed assumption proposed by Papke et al. that the extrinsic information is Gaussian distributed. This study proposes a novel scaling factor approach for reducing both the overestimation of reliability values and the correlation between the intrinsic and extrinsic information. Explicit formulae for computing the scaling factors are derived based on mathematical statistics. A key difference compared to the scaling factor method of Papke et al. is that the proposed scaling factors can be computed off-line. The numerical results show that when implemented in the decoding algorithm of block component codes, the proposed scaling factor approach improves the performance of turbo decoding over additive white Gaussian noise and Rayleigh fading channels. It is superior than the method by Papke et al. in both performance and complexity.
This paper aims to the improve the data rate for the visible light communication system using LED array and high-speed camera. Previously, we have proposed the decoding algorithm using inverted signals for driving sit...
详细信息
ISBN:
(纸本)9781467349420
This paper aims to the improve the data rate for the visible light communication system using LED array and high-speed camera. Previously, we have proposed the decoding algorithm using inverted signals for driving situation. However, using this method the data rate become a half, because we transmit original signals and inverted signals alternately for LED array tracking. In this paper, we propose the data rate improving method for overlay coding which is coding method that overlay two data which are called as the long range data and the short range data. In the proposed method, for the long range data, we transmit original signals and inverted signals alternately. On the other hand, for the short range data, we transmit only original signals while we transmit inverted signals of long range data. We confirm that we can improve data rate as compared with the previous method.
Linear programming (LP) decoding for low density parity check (LDPC) codes proposed by Feldman et al. has attracted considerable attention in recent years. Despite having theoretical guarantees in some regimes, at low...
详细信息
ISBN:
(纸本)9781467345378
Linear programming (LP) decoding for low density parity check (LDPC) codes proposed by Feldman et al. has attracted considerable attention in recent years. Despite having theoretical guarantees in some regimes, at low SNRs LP decoding is observed to have worse error performance than belief propagation (BP) decoding. In this paper, we present a novel decoding algorithm obtained by trying to solve a non-convex optimization problem using the alternating direction method of multipliers (ADMM). This non-convex problem is constructed by adding an l_1 penalty term to the LP decoding objective. The goal of the penalty term is to make "pseudocodewords", which are the non-integer vertices of the LP relaxation to which the LP decoder fails, more costly. We name this the "l_1 penalized decoder". We also develop a reweighted LP decoding algorithm base on this l_1 penalized objective. We show that this reweighted LP has an improved theoretical recovery threshold compared to the original LP. In addition, simulations show that, in comparison to LP decoding, these two decoders both achieve significantly lower error rates and are not observed to have an "error floor". In particular, the l_1 penalized decoder meets or outperforms the BP decoder at all SNRs.
Flash memory comprises of grid of cells arranged in a rectangular lattice. A cell is a floating gate and the information is stored as charge in these floating gates. A multi-level-cell (MLC) stores more than one bit p...
详细信息
ISBN:
(纸本)9781424492688
Flash memory comprises of grid of cells arranged in a rectangular lattice. A cell is a floating gate and the information is stored as charge in these floating gates. A multi-level-cell (MLC) stores more than one bit per cell. Programming of a cell in NAND Flash is attained by Fowler-Nordhiem tunneling till the ideal programmed voltage is attained. However, due to programming time constraints, some tolerance is accepted and the actual programmed voltage is allowed to be within some range of the ideal value. The read level is a random variable with some distribution around the mean programming level. Errors occur during reads because of overlaps of the level distributions. If the raw bit error rate has to be kept low, the distributions must be narrow. One of the impairment which broadens the distributions is the capacitive coupling between neighboring cells. This phenomenon called as inter-cell-interference due to floating-gate to floating-gate coupling can be from mild to extreme. To combat this effect, constrained coding is a possible solution. Constrained coding entails forbidding certain adjacent-cell charge-level combinations. There can be various types of constrained codes, one type of constrained codes assumes that level information is available while decoding all pages [1]. However, due to read latency requirements, level information may not be available while reading all pages. In this paper, constrained codes are proposed which do not need level information while decoding all pages and hence the average read latency is reduced. Error propagation is a crucial degrading factor for constrained decoding and the codes proposed are robust to channel noise. A new decoding algorithm which keeps synchronization which is crucial to contain error propagation is also proposed.
We demonstrate a lensfree on-chip fluorescent microscopy platform that can image fluorescently labeled cells over similar to 60 mm(2) field-of-view with 5-fold higher density of fiber-optic waveguides in its top face...
详细信息
ISBN:
(纸本)9781424441228
We demonstrate a lensfree on-chip fluorescent microscopy platform that can image fluorescently labeled cells over similar to 60 mm(2) field-of-view with <4 mu m spatial resolution. In this lensfree imaging system, micro-objects of interest are directly located on tapered fiber-optic faceplate which has > 5-fold higher density of fiber-optic waveguides in its top facet compared to the bottom facet. For excitation, an incoherent compared to the bottom facet. For excitation, an incoherent light source (e.g. a simple light emitting diode - LED) is used to pump fluorescent objects through a glass hemi-sphere interface. Upon interacting with the entire sample volume, the excitation light is rejected by total internal reflection process occurring at the bottom of the sample substrate. Fluorescent emission from the objects is then collected by the smaller facet of the tapered faceplate and is delivered to a detector-array with an image magnification of similar to 2.4X. A compressive sampling based decoding algorithm is used for sparse signal recovery, which further increases the space-bandwidth-product of our lensfree on-chip fluorescent imager. We validated the performance of this lensfree imaging platform using fluorescent micro-particles as well as labeled water-borne parasites (e.g. Giardia Muris cysts). Such a compact and wide-field fluorescent microscopy platform could be valuable for cytometry and rare cell imaging applications as well as for micro array research.
In the past decade the field of neural interface systems has enjoyed an increase in attention from the scientific community and the general public, in part due to the enormous potential that such systems have to incre...
详细信息
ISBN:
(纸本)9781424441242
In the past decade the field of neural interface systems has enjoyed an increase in attention from the scientific community and the general public, in part due to the enormous potential that such systems have to increase the quality of life for paralyzed patients. While significant progress has been made, serious challenges remain to be addressed from both biological and engineering perspectives. A key issue is how to optimize the decoding of neural information, such that neural signals are correctly mapped to effectors that interact with the outside world - like robotic hands and limbs or the patient's own muscles. Here we present some recent progress on tackling this problem by applying the latest developments in machine learning. Neural data was collected from macaque monkeys performing a real-time hand grasp decoding task. Signals were recorded via chronically implanted electrodes in the anterior intraparietal cortex (AIP) and ventral premotor cortex (F5), brain areas that are known to be involved in the transformation of visual signals into hand grasping instructions. We present a comparative study of different classical machine learning methods with an application of decoding of hand postures, as well as a new approach for more robust decoding. Results suggests that combining data-driven algorithmic approaches with well-known parametric methods could lead to better performing and more robust learners, which may have direct implications for future clinical devices.
暂无评论