skip to main content

Title: General strong polarization
Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix M, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2=(1011) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization. While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with G2 such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), thereby resolving a major theoretical challenge associated with the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more » more general, our proofs of strong polarization are (in our view) also much simpler and modular. Key to our proof is a notion of local polarization that only depends on the evolution of the martingale in a single time step. Our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels. « less
; ; ; ;
Award ID(s):
1715187 1717134
Publication Date:
Journal Name:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing,
Page Range or eLocation-ID:
485 to 492
Sponsoring Org:
National Science Foundation
More Like this
  1. We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability exp(-N^{Omega(1)}) for codes of length N). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the time-local behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the "Arikan martingale", exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes thatmore »achieve failure probability exp(-N^{beta}) for any beta < 1 while converging to capacity at block length polynomial in the gap to capacity. Finally we also show that the "local" approach can be combined with any analysis of failure probability of an arbitrary polar code to get essentially the same failure probability while achieving block length polynomial in the gap to capacity.« less
  2. In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any e>0.085, we show an explicit sequence of capacity-achieving codes with all the column wights of the generator matrix upper bounded by (log N) to the power (1+e), where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.
  3. Generative neural networks have been empirically found very promising in providing effective structural priors for compressed sensing, since they can be trained to span low-dimensional data manifolds in high-dimensional signal spaces. Despite the non-convexity of the resulting optimization problem, it has also been shown theoretically that, for neural networks with random Gaussian weights, a signal in the range of the network can be efficiently, approximately recovered from a few noisy measurements. However, a major bottleneck of these theoretical guarantees is a network expansivity condition: that each layer of the neural network must be larger than the previous by a logarithmic factor. Our main contribution is to break this strong expansivity assumption, showing that constant expansivity suffices to get efficient recovery algorithms, besides it also being information-theoretically necessary. To overcome the theoretical bottleneck in existing approaches we prove a novel uniform concentration theorem for random functions that might not be Lipschitz but satisfy a relaxed notion which we call "pseudo-Lipschitzness." Using this theorem we can show that a matrix concentration inequality known as the Weight Distribution Condition (WDC), which was previously only known to hold for Gaussian matrices with logarithmic aspect ratio, in fact holds for constant aspect ratios too. Sincemore »the WDC is a fundamental matrix concentration inequality in the heart of all existing theoretical guarantees on this problem, our tighter bound immediately yields improvements in all known results in the literature on compressed sensing with deep generative priors, including one-bit recovery, phase retrieval, low-rank matrix recovery, and more.« less
  4. Conventional lithium-ion batteries are unable to meet the increasing demands for high-energy storage systems, because of their limited theoretical capacity. 1 In recent years, intensive attention has been paid to enhancing battery energy storage capability to satisfy the increasing energy demand in modern society and reduce the average energy capacity cost. Among the candidates for next generation high energy storage systems, the lithium sulfur battery is especially attractive because of its high theoretical specific energy (around 2600 W h kg-1) and potential cost reduction. In addition, sulfur is a cost effective and environmentally friendly material due to its abundance and low-toxicity. 2 Despite all of these advantages, the practical application of lithium sulfur batteries to date has been hindered by a series of obstacles, including low active material loading, poor cycle life, and sluggish sulfur conversion kinetics. 3 Achieving high mass loading cathode in the traditional 2D planar thick electrode has been challenged. The high distorsion of the traditional planar thick electrodes for ion/electron transfer leads to the limited utilization of active materials and high resistance, which eventually results in restricted energy density and accelerated electrode failure. 4 Furthermore, of the electrolyte to pores in the cathode and utilization ratiomore »of active materials. Catalysts such as MnO 2 and Co dopants were employed to accelerate the sulfur conversion reaction during the charge and discharge process. 5 However, catalysts based on transition metals suffer from poor electronic conductivity. Other catalysts such as transition metal dopants are also limited due to the increased process complexities. . In addition, the severe shuttle effects in Li-S batteries may lead to fast failures of the battery. Constructing a protection layer on the separator for limiting the transmission of soluble polysulfides is considered an effective way to eliminate the shuttle phenomenon. However, the soluble sulfides still can largely dissolve around the cathode side causing the sluggish reaction condition for sulfur conversion. 5 To mitigate the issues above, herein we demonstrate a novel sulfur electrode design strategy enabled by additive manufacturing and oxidative vapor deposition (oCVD). Specifically, the electrode is strategically designed into a hierarchal hollow structure via stereolithography technique to increase sulfur usage. The active material concentration loaded to the battery cathode is controlled precisely during 3D printing by adjusting the number of printed layers. Owing to its freedom in geometry and structure, the suggested design is expected to improve the Li ions and electron transport rate considerably, and hence, the battery power density. The printed cathode is sintered at 700 °C at N 2 atmosphere to achieve carbonization of the cathode during which intrinsic carbon defects (e.g., pentagon carbon) as catalytic defect sites are in-situ generated on the cathode. The intrinsic carbon defects equipped with adequate electronic conductivity. The sintered 3D cathode is then transferred to the oCVD chamber for depositing a thin PEDOT layer as a protection layer to restrict dissolutions of sulfur compounds in the cathode. Density functional theory calculation reveals the electronic state variance between the structures with and without defects, the structure with defects demonstrates the higher kinetic condition for sulfur conversion. To further identify the favorable reaction dynamic process, the in-situ XRD is used to characterize the transformation between soluble and insoluble polysulfides, which is the main barrier in the charge and discharge process of Li-S batteries. The results show the oCVD coated 3D printed sulfur cathode exhibits a much higher kinetic process for sulfur conversion, which benefits from the highly tailored hierarchal hollow structure and the defects engineering on the cathode. Further, the oCVD coated 3D printed sulfur cathode also demonstrates higher stability during long cycling enabled by the oCVD PEDOT protection layer, which is verified by an absorption energy calculation of polysulfides at PEDOT. Such modeling and analysis help to elucidate the fundamental mechanisms that govern cathode performance and degradation in Li-S batteries. The current study also provides design strategies for the sulfur cathode as well as selection approaches to novel battery systems. References: Bhargav, A., (2020). Lithium-Sulfur Batteries: Attaining the Critical Metrics. Joule 4 , 285-291. Chung, S.-H., (2018). Progress on the Critical Parameters for Lithium–Sulfur Batteries to be Practically Viable. Advanced Functional Materials 28 , 1801188. Peng, H.-J.,(2017). Review on High-Loading and High-Energy Lithium–Sulfur Batteries. Advanced Energy Materials 7 , 1700260. Chu, T., (2021). 3D printing‐enabled advanced electrode architecture design. Carbon Energy 3 , 424-439. Shi, Z., (2021). Defect Engineering for Expediting Li–S Chemistry: Strategies, Mechanisms, and Perspectives. Advanced Energy Materials 11 . Figure 1« less
  5. With the rapid growth of Internet of Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and low-overhead uplink scheduling algorithm that is suitable for large-scale IoT applications with limited amount of coordination from the central controller. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting and wireless channel probing. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacity-achieving algorithm allow us to develop an efficient and low-overhead scheduling algorithm that can strictly satisfymore »the sampling constraint with asymptotically diminishing throughput loss. Moreover, the throughput performance of our proposed algorithm is independent of the number of users, a highly desirable property in large-scale IoT systems. Finally, we perform extensive simulations to validate our theoretical results.« less