Source author record

Brian M. Kurkoski

Brian M. Kurkoski appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT eess.SP math.ST Statistics Theory Artificial Intelligence Machine Learning

Catalog footprint

What is connected

11works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

Overflow-Avoiding Memory AMP

Approximate Message Passing (AMP) type algorithms are widely used for signal recovery in high-dimensional noisy linear systems. Recently, a principle called Memory AMP (MAMP) was proposed. Leveraging this principle, the gradient descent MAMP (GD-MAMP) algorithm was designed, inheriting the strengths of AMP and OAMP/VAMP. In this paper, we first provide an overflow-avoiding GD-MAMP (OA-GD-MAMP) to address the overflow problem that arises from some intermediate variables exceeding the range of floating point numbers. Second, we develop a complexity-reduced GD-MAMP (CR-GD-MAMP) to reduce the number of matrix-vector products per iteration by 1/3 (from 3 to 2) with little to no impact on the convergence speed.

preprint2022arXiv

Memory AMP

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results' validity and accuracy.

preprint2022arXiv

Sufficient Statistic Memory Approximate Message Passing

Approximate message passing (AMP) type algorithms have been widely used in the signal reconstruction of certain large random linear systems. A key feature of the AMP-type algorithms is that their dynamics can be correctly described by state evolution. However, state evolution does not necessarily guarantee the convergence of iterative algorithms. To solve the convergence problem of AMP-type algorithms in principle, this paper proposes a memory AMP (MAMP) under a sufficient statistic condition, named sufficient statistic MAMP (SS-MAMP). We show that the covariance matrices of SS-MAMP are L-banded and convergent. Given an arbitrary MAMP, we can construct the SS-MAMP by damping, which not only ensures the convergence, but also preserves the orthogonality, i.e., its dynamics can be correctly described by state evolution.

preprint2021arXiv

Construction D' Lattices for Power-Constrained Communications

Designs and methods for nested lattice codes using Construction D' lattices for coding and convolutional code lattices for shaping are described. Two encoding methods and a decoding algorithm for Construction D' coding lattices that can be used with shaping lattices for power-constrained channels are given. We construct nested lattice codes with good coding properties, a high shaping gain, and low-complexity encoding and decoding. Convolutional code generator polynomials for Construction A lattices with the greatest shaping gain are given, as a result of an extensive search. It is shown that rate 1/3 convolutional codes provide a more favorable performance-complexity trade-off than rate 1/2 convolutional codes. Tail-biting convolutional codes have higher shaping gain than that of zero-tailed convolutional codes. A design for quasi-cyclic low-density parity-check (QC-LDPC) codes to form Construction D' lattices which have efficient encoding and indexing is presented. The resulting QC-LDPC Construction D' lattices are evaluated using four shaping lattices: the $E_8$ lattice, the $BW_{16}$ lattice, the Leech lattice and our best-found convolutional code lattice, showing a shaping gain of approximately 0.65 dB, 0.86 dB, 1.03 dB and 1.25 dB at dimension 2304.

preprint2021arXiv

Design of Polar Code Lattices of Small Dimension

Polar code lattices are formed from binary polar codes using Construction D. In this paper, we propose a design technique for finite-dimension polar code lattices. The dimension $n$ and target probability of decoding error are parameters for this design. To select the rates of the Construction D component codes, rather than using the capacity as in past work, we use the explicit finite-length properties of the polar code. Under successive cancellation decoding, density evolution allows choosing code rates that satisfy the equal error probability rule. At an error-rate of $10^{-4}$, a dimension $n=128$ polar code lattice achieves a VNR of 2.5 dB, within 0.2 dB of the best-known BCH code lattice, but with significantly lower decoding complexity.

preprint2020arXiv

Opportunistic Cooperation Strategies for Multiple Access Relay Channels with Compute-and-Forward

This paper studies the application of compute-and-forward to multiple access relay channels (MARC). Despite its promising advantage of improving network throughput, it is not straightforward to apply compute-and-forward to the MARC. This paper proposes two efficient cooperation strategies for the MARC with compute-and-forward. Both proposed strategies are opportunistic in the sense that the cooperation between the relay and the destination are performed only when it is needed for the sake of high transmission efficiency. In the first strategy, the relay helps the destination by sending its local optimal integer coefficient vector without taking into account that the resulting integer coefficient matrix at the destination is full rank. In contrast, in the second strategy, the relay forwards its ``best'' coefficient vector that always ensures a full rank coefficient matrix at the destination. Both of the proposed strategies achieve twice the network throughput of the existing strategies at high signal-to-noise power ratio (SNR). They also have lower outage probability, independent of relay placement. Furthermore, the first strategy nearly achieves diversity gain of order two, and the second one achieves exactly the diversity gain of order two, which cannot be achieved by the existing strategies.

preprint2016arXiv

Encoding and Indexing of Lattice Codes

Encoding and indexing of lattice codes is generalized from self-similar lattice codes to a broader class of lattices. If coding lattice $Λ_{\textrm{c}}$ and shaping lattice $Λ_{\textrm{s}}$ satisfy $Λ_{\textrm{s}} \subseteq Λ_{\textrm{c}}$, then $Λ_{\textrm{c}} / Λ_{\textrm{s}}$ is a quotient group that can be used to form a (nested) lattice code $\mathcal{C}$. Conway and Sloane's method of encoding and indexing does not apply when the lattices are not self-similar. Results are provided for two classes of lattices. (1) If $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ both have generator matrices in triangular form, then encoding is always possible. (2) When $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ are described by full generator matrices, if a solution to a linear diophantine equation exists, then encoding is possible. In addition, special cases where $\mathcal{C}$ is a cyclic code are also considered. A condition for the existence of a group homomorphism between the information and $\mathcal{C}$ is given. The results are applicable to a variety of coding lattices, including Construction A, Construction D and LDLCs. The $D_4$, $E_8$ and convolutional code lattices are shown to be good choices for the shaping lattice. Thus, a lattice code $\mathcal{C}$ can be designed by selecting $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ separately, avoiding competing design requirements of self-similar lattice codes.

preprint2016arXiv

Low-Dimensional Shaping for High-Dimensional Lattice Codes

We propose two low-complexity lattice code constructions that have competitive coding and shaping gains. The first construction, named systematic Voronoi shaping, maps short blocks of integers to the dithered Voronoi integers, which are dithered integers that are uniformly distributed over the Voronoi region of a low-dimensional shaping lattice. Then, these dithered Voronoi integers are encoded using a high-dimensional lattice retaining the same shaping and coding gains of low and high-dimensional lattices. A drawback to this construction is that there is no isomorphism between the underlying message and the lattice code, preventing its use in applications such as compute-and- forward. Therefore we propose a second construction, called mixed nested lattice codes, in which a high-dimensional coding lattice is nested inside a concatenation of low-dimensional shaping lattices. This construction not only retains the same shaping/coding gains as first construction but also provides the desired algebraic structure. We numerically study these methods, for point-to-point channels as well as compute-and-forward using low-density lattice codes (LDLCs) as coding lattices and E8 and Barnes-Wall as shaping lattices. Numerical results indicate a shaping gain of up to 0.86 dB, compared to the state-of-the-art of 0.4 dB; furthermore, the proposed method has lower complexity than state-of-the-art approaches.

preprint2014arXiv

Quantization of Binary-Input Discrete Memoryless Channels

The quantization of the output of a binary-input discrete memoryless channel to a smaller number of levels is considered. An algorithm which finds an optimal quantizer, in the sense of maximizing mutual information between the channel input and the quantizer output is given. This result holds for arbitrary channels, in contrast to previous results for restricted channels or a restricted number of quantizer outputs. In the worst case, the algorithm complexity is cubic $M^3$ in the number of channel outputs $M$. Optimality is proved using the theorem of Burshtein, Della Pietra, Kanevsky, and Nádas for mappings which minimize average impurity for classification and regression trees.

preprint2011arXiv

Threshold Improvement of Low-Density Lattice Codes via Spatial Coupling

Spatially-coupled low-density lattice codes (LDLC) are constructed using protographs. Using Monte Carlo density evolution using single-Gaussian messages, we observe that the threshold of the spatially-coupled LDLC is within 0.22 dB of capacity of the unconstrained power channel. This is in contrast with a 0.5 dB noise threshold for the conventional LDLC lattice construction.

preprint2010arXiv

Rewritable Codes for Flash Memories Based Upon Lattices, and an Example Using the E8 Lattice

A rewriting code construction for flash memories based upon lattices is described. The values stored in flash cells correspond to lattice points. This construction encodes information to lattice points in such a way that data can be written to the memory multiple times without decreasing the cell values. The construction partitions the flash memory's cubic signal space into blocks. The minimum number of writes is shown to be linear in one of the code parameters. An example using the E8 lattice is given, with numerical results.