214 results on '"Calderbank, Robert"'
Search Results
2. Eliminating Media Noise While Preserving Storage Capacity: Reconfigurable Constrained Codes for Two-Dimensional Magnetic Recording
- Author
-
Guzel, Iven, Özbayrak, Doğukan, Calderbank, Robert, and Hareedy, Ahmed
- Subjects
Computer Science - Information Theory ,Electrical Engineering and Systems Science - Signal Processing - Abstract
Magnetic recording devices are still competitive in the storage density race with solid-state devices thanks to new technologies such as two-dimensional magnetic recording (TDMR). Advanced data processing schemes are needed to guarantee reliability in TDMR. Data patterns where a bit is surrounded by complementary bits at the four positions with Manhattan distance $1$ on the TDMR grid are called plus isolation (PIS) patterns, and they are error-prone. Recently, we introduced lexicographically-ordered constrained (LOCO) codes, namely optimal plus LOCO (OP-LOCO) codes, that prevent these patterns from being written in a TDMR device. However, in the high-density regime or the low-energy regime, additional error-prone patterns emerge, specifically data patterns where a bit is surrounded by complementary bits at only three positions with Manhattan distance $1$, and we call them incomplete plus isolation (IPIS) patterns. In this paper, we present capacity-achieving codes that forbid both PIS and IPIS patterns in TDMR systems with wide read heads. We collectively call the PIS and IPIS patterns rotated T isolation (RTIS) patterns, and we call the new codes optimal T LOCO (OT-LOCO) codes. We analyze OT-LOCO codes and present their simple encoding-decoding rule that allows reconfigurability. We also present a novel bridging idea for these codes to further increase the rate. Our simulation results demonstrate that OT-LOCO codes are capable of eliminating media noise effects entirely at practical TD densities with high rates. To further preserve the storage capacity, we suggest using OP-LOCO codes early in the device lifetime, then employing the reconfiguration property to switch to OT-LOCO codes later. While the point of reconfiguration on the density/energy axis is decided manually at the moment, the next step is to use machine learning to take that decision based on the TDMR device status., Comment: 15 pages (double column), 11 figures, submitted to the IEEE Transactions on Magnetics (TMAG). arXiv admin note: text overlap with arXiv:2010.10686
- Published
- 2023
3. Use of a Digital Modified Checklist for Autism in Toddlers – Revised with Follow-up to Improve Quality of Screening for Autism
- Author
-
Campbell, Kathleen, Carpenter, Kimberly L.H., Espinosa, Steven, Hashemi, Jordan, Qiu, Qiang, Tepper, Mariano, Calderbank, Robert, Sapiro, Guillermo, Egger, Helen L., Baker, Jeffrey P., and Dawson, Geraldine
- Published
- 2017
- Full Text
- View/download PDF
4. LDPC Decoders Prefer More Reliable Parity Bits: Unequal Data Protection Over BSC
- Author
-
Dabak, Beyza, Tiryaki, Ece, Calderbank, Robert, and Hareedy, Ahmed
- Subjects
FOS: Computer and information sciences ,Information Theory (cs.IT) ,Computer Science - Information Theory - Abstract
Low-density parity-check (LDPC) codes are specified by graphs, and are the error correction technique of choice in many communications and data storage contexts. Message passing decoders diffuse information carried by parity bits into the payload, and this paper measures the value of engineering parity bits to be more reliable than message bits. We consider the binary symmetric channel (BSC) and measure the impact of unequal data protection on the threshold of a regular LDPC code. Our analysis also includes doping where the parity bits are known to the decoder. We investigate BSC with Gallager-A decoder, with a $3$-level-alphabet decoder, and with a full belief propagation decoder. We demonstrate through theoretical analysis and simulation that non-equiprobable inputs lead to significant improvements both in the threshold and in the speed with which the decoder converges. We also show that all these improvements are possible even with a simple $3$-level-alphabet decoder., 8 pages (double column), 1 figure, submitted to the International Symposium on Topics in Coding (ISTC)
- Published
- 2023
5. Efficient Constrained Codes That Enable Page Separation in Modern Flash Memories
- Author
-
Hareedy, Ahmed, Zheng, Simeng, Siegel, Paul, and Calderbank, Robert
- Subjects
Signal Processing (eess.SP) ,FOS: Computer and information sciences ,Information Theory (cs.IT) ,Computer Science - Information Theory ,FOS: Electrical engineering, electronic engineering, information engineering ,Electrical Engineering and Systems Science - Signal Processing - Abstract
The pivotal storage density win achieved by solid-state devices over magnetic devices recently is a result of multiple innovations in physics, architecture, and signal processing. Constrained coding is used in Flash devices to increase reliability via mitigating inter-cell interference. Recently, capacity-achieving constrained codes were introduced to serve that purpose. While these codes result in minimal redundancy, they result in non-negligible complexity increase and access speed limitation since pages cannot be read separately. In this paper, we suggest new constrained coding schemes that have low-complexity and preserve the desirable high access speed in modern Flash devices. The idea is to eliminate error-prone patterns by coding data either only on the left-most page (binary coding) or only on the two left-most pages ($4$-ary coding) while leaving data on all the remaining pages uncoded. Our coding schemes are systematic and capacity-approaching. We refer to the proposed schemes as read-and-run (RR) constrained coding schemes. The $4$-ary RR coding scheme is introduced to limit the rate loss. We analyze the new RR coding schemes and discuss their impact on the probability of occurrence of different charge levels. We also demonstrate the performance improvement achieved via RR coding on a practical triple-level cell Flash device., 30 pages (single column), 5 figures, submitted to the IEEE Transactions on Communications (TCOM). arXiv admin note: substantial text overlap with arXiv:2111.07415
- Published
- 2023
6. On block coherence of frames
- Author
-
Calderbank, Robert, Thompson, Andrew, and Xie, Yao
- Published
- 2015
- Full Text
- View/download PDF
7. Reed Muller Sensing Matrices and the LASSO : (Invited Paper)
- Author
-
Calderbank, Robert, Jafarpour, Sina, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carlet, Claude, editor, and Pott, Alexander, editor
- Published
- 2010
- Full Text
- View/download PDF
8. Divisible Codes for Quantum Computation
- Author
-
Hu, Jingzhen, Liang, Qingzhong, and Calderbank, Robert
- Subjects
FOS: Computer and information sciences ,Quantum Physics ,Information Theory (cs.IT) ,Computer Science - Information Theory ,FOS: Physical sciences ,Quantum Physics (quant-ph) - Abstract
Divisible codes are defined by the property that codeword weights share a common divisor greater than one. They are used to design signals for communications and sensing, and this paper explores how they can be used to protect quantum information as it is transformed by logical gates. Given a CSS code $\mathcal{C}$, we derive conditions that are both necessary and sufficient for a transversal diagonal physical operator $U_Z$ to preserve $\mathcal{C}$ and induce $U_L$. The group of $Z$-stabilizers in a CSS code $\mathcal{C}$ is determined by the dual of a classical $[n, k_1]$ binary code $\mathcal{C}_1$, and the group of $X$-stabilizers is determined by a classical $[n, k_2]$ binary code $\mathcal{C}_2$ that is contained in $\mathcal{C}_1$. The requirement that a diagonal physical operator $U_Z$ fixes a CSS code $\mathcal{C}$ leads to constraints on the congruence of weights in cosets of $\mathcal{C}_2$. These constraints are a perfect fit to divisible codes, and represent an opportunity to take advantage of the extensive literature on classical codes with two or three weights. We construct new families of CSS codes using cosets of the first order Reed Muller code defined by quadratic forms. We provide a simple alternative to the standard method of deriving the coset weight distributions (based on Dickson normal form) that may be of independent interest. Finally, we develop an approach to circumventing the Eastin-Knill Theorem which states that no QECC can implement a universal set of logical gates through transversal gates alone. The essential idea is to design stabilizer codes in layers, with $N_1$ inner qubits and $N_2$ outer qubits, and to assemble a universal set of fault tolerant gates on the inner qubits., Jingzhen Hu and Qingzhong Liang contribute equally to this work. 11 pages. Comments welcome!
- Published
- 2022
9. Stable phase retrieval for infinite dimensional subspaces of $L_2(\mathbb{R})$
- Author
-
Calderbank, Robert, Daubechies, Ingrid, Freeman, Daniel, and Freeman, Nikki
- Subjects
Mathematics - Functional Analysis ,42C15, 46B42, 94A20 ,FOS: Mathematics ,FOS: Physical sciences ,Mathematical Physics (math-ph) ,Mathematical Physics ,Functional Analysis (math.FA) - Abstract
Phase retrieval is known to always be unstable when using a frame or continuous frame for an infinite dimensional Hilbert space. We consider a generalization of phase retrieval to the setting of subspaces of $L_2$ which coincides with using a continuous frame for phase retrieval when the subspace is the range of the analysis operator of a continuous frame. We then prove that there do exist infinite dimensional subspaces of $L_2$ where phase retrieval is stable. That is, we give a method for constructing an infinite dimensional subspace $Y\subseteq L_2$ such that there exists $C\geq 1$ so that $$\min\big(\big\|f-g\big\|_{L_2},\big\|f+g\big\|_{L_2}\big)\leq C \big\| |f|-|g| \big\|_{L_2} \qquad\textrm{ for all }f,g\in Y. $$ This construction also leads to new results on uniform stability of phase retrieval in finite dimensions. Our construction has a deterministic component and a random component. When using sub-Gaussian random variables we achieve phase retrieval with high probability and stability constant independent of the dimension $n$ when using $m$ on the order of $n$ random vectors. Without sub-Gaussian or any other higher moment assumptions, we are able to achieve phase retrieval with high probability and stability constant independent of the dimension $n$ when using $m$ on the order of $n\log(n)$ random vectors., 27 pages
- Published
- 2022
10. Binary Subspace Chirps.
- Author
-
Pllaha, Tefjol, Tirkkonen, Olav, and Calderbank, Robert
- Subjects
REED-Muller codes ,SYMPLECTIC geometry ,DECODING algorithms ,QUANTUM computing ,ERROR probability ,COMPRESSED sensing - Abstract
We describe in detail the interplay between binary symplectic geometry and notions from quantum computation, with the ultimate goal of constructing highly structured codebooks. The Binary Chirps (BCs) are Complex Grassmannian Lines in $N = 2^{m}$ dimensions used in deterministic compressed sensing and random/unsourced multiple access in wireless networks. Their entries are fourth roots of unity and can be described in terms of second order Reed-Muller codes. The Binary Subspace Chirps (BSSCs) are a unique collection of BCs of ranks ranging from $r=0$ to $r = m$ , embedded in $N$ dimensions according to an on-off pattern determined by a rank $r$ binary subspace. This yields a codebook that is asymptotically 2.38 times larger than the codebook of BCs, has the same minimum chordal distance as the codebook of BCs, and the alphabet is minimally extended from $\{\pm 1,\pm i\}$ to $\{\pm 1,\pm i, 0\}$. Equivalently, we show that BSSCs are stabilizer states, and we characterize them as columns of a well-controlled collection of Clifford matrices. By construction, the BSSCs inherit all the properties of BCs, which in turn makes them good candidates for a variety of applications. For applications in wireless communication, we use the rich algebraic structure of BSSCs to construct a low complexity decoding algorithm that is reliable against Gaussian noise. In simulations, BSSCs exhibit an error probability comparable or slightly lower than BCs, both for single-user and multi-user transmissions. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. Two are better than one: Fundamental parameters of frame coherence
- Author
-
Bajwa, Waheed U., Calderbank, Robert, and Mixon, Dustin G.
- Published
- 2012
- Full Text
- View/download PDF
12. Climbing the Diagonal Clifford Hierarchy
- Author
-
Hu, Jingzhen, Liang, Qingzhong, and Calderbank, Robert
- Subjects
FOS: Computer and information sciences ,Quantum Physics ,Computer Science::Emerging Technologies ,Information Theory (cs.IT) ,Computer Science - Information Theory ,FOS: Physical sciences ,Quantum Physics (quant-ph) ,Hardware_LOGICDESIGN - Abstract
Magic state distillation and the Shor factoring algorithm make essential use of logical diagonal gates. We introduce a method of synthesizing CSS codes that realize a target logical diagonal gate at some level $l$ in the Clifford hierarchy. The method combines three basic operations: concatenation, removal of $Z$-stabilizers, and addition of $X$-stabilizers. It explicitly tracks the logical gate induced by a diagonal physical gate that preserves a CSS code. The first step is concatenation, where the input is a CSS code and a physical diagonal gate at level $l$ inducing a logical diagonal gate at the same level. The output is a new code for which a physical diagonal gate at level $l+1$ induces the original logical gate. The next step is judicious removal of $Z$-stabilizers to increase the level of the induced logical operator. We identify three ways of climbing the logical Clifford hierarchy from level $l$ to level $l+1$, each built on a recursive relation on the Pauli coefficients of the induced logical operators. Removal of $Z$-stabilizers may reduce distance, and the purpose of the third basic operation, addition of $X$-stabilizers, is to compensate for such losses. For the coherent noise model, we describe how to switch between computation and storage of intermediate results in a decoherence-free subspace by simply applying Pauli $X$ matrices. The approach to logical gate synthesis taken in prior work focuses on the code states, and results in sufficient conditions for a CSS code to be fixed by a transversal $Z$-rotation. In contrast, we derive necessary and sufficient conditions by analyzing the action of a transversal diagonal gate on the stabilizer group that determines the code. The power of our approach is demonstrated by two proofs of concept: the $[[2^{l+1}-2,2,2]]$ triorthogonal code family, and the $[[2^m,\binom{m}{r},2^{\min\{r,m-r\}}]]$ quantum Reed-Muller code family., Jingzhen Hu and Qingzhong Liang contribute equally to this work. 15 pages, two columns, 8 figures, and 1 table. Comments welcome! This work is an application based on the mathematical framework introduced in arXiv:2109.13481
- Published
- 2021
13. Breaking the Computational Bottleneck: Design of Near-Optimal High-Memory Spatially-Coupled Codes
- Author
-
Yang, Siyi, Hareedy, Ahmed, Calderbank, Robert, and Dolecek, Lara
- Subjects
FOS: Computer and information sciences ,Information Theory (cs.IT) ,Computer Science - Information Theory - Abstract
Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging. We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interests, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems., 26 pages, 30 figures, 2 tables, the manuscript has been submitted to IEEE Transactions on Information Theory. arXiv admin note: substantial text overlap with arXiv:2101.09962
- Published
- 2021
14. Unitary design of radar waveform diversity sets
- Author
-
Qureshi, Tariq R., Zoltowski, Michael D., Calderbank, Robert, and Pezeshki, Ali
- Published
- 2011
- Full Text
- View/download PDF
15. Learning to Equalize OTFS.
- Author
-
Zhou, Zhou, Liu, Lingjia, Xu, Jiarui, and Calderbank, Robert
- Abstract
Orthogonal Time Frequency Space (OTFS) is a novel framework that processes modulation symbols via a time-independent channel characterized by the delay-Doppler domain. The conventional waveform, orthogonal frequency division multiplexing (OFDM), requires tracking frequency selective fading channels over the time, whereas OTFS benefits from full time-frequency diversity by leveraging appropriate equalization techniques. In this paper, we consider a neural network-based supervised learning framework for OTFS equalization. Learning of the introduced neural network is conducted in each OTFS frame fulfilling an online learning framework: the training and testing datasets are within the same OTFS-frame over the air. Utilizing reservoir computing, a special recurrent neural network, the resulting one-shot online learning is sufficiently flexible to cope with channel variations among different OTFS frames (e.g., due to the link/rank adaptation and user scheduling in cellular networks). The proposed method does not require explicit channel state information (CSI) and simulation results demonstrate a lower bit error rate (BER) than conventional equalization methods in the low signal-to-noise (SNR) regime under large Doppler spreads. When compared with its neural network-based counterparts for OFDM, the introduced approach for OTFS will lead to a better tradeoff between the processing complexity and the equalization performance. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
16. The Secret Arithmetic of Patterns: A General Method for Designing Constrained Codes Based on Lexicographic Indexing.
- Author
-
Hareedy, Ahmed, Dabak, Beyza, and Calderbank, Robert
- Subjects
MAGNETIC storage ,DATA transmission systems ,DATA warehousing ,TWO-dimensional bar codes ,OPTICAL disks ,LINEAR codes ,ARITHMETIC - Abstract
Constrained codes are used to prevent errors from occurring in various data storage and data transmission systems. They can help in increasing the storage density of magnetic storage devices, in managing the lifetime of solid-state storage devices, and in increasing the reliability of data transmission over wires. Over the years, designing practical (complexity-wise) capacity-achieving constrained codes has been an area of research gaining significant interest. We recently designed various constrained codes based on lexicographic indexing. We introduced binary symmetric lexicographically-ordered constrained (S-LOCO) codes, $q$ -ary asymmetric LOCO (QA-LOCO) codes, and a class of two-dimensional LOCO (TD-LOCO) codes. These families of codes achieve capacity with simple encoding and decoding, and they are easy to reconfigure. We demonstrated that these codes can contribute to notable density and lifetime gains in magnetic recording (MR) and Flash systems, and they find application in other systems too. In this paper, we generalize our work on LOCO codes by presenting a systematic method that guides the code designer to build any constrained code based on lexicographic indexing once the finite set of data patterns to forbid is known. In particular, we connect the set of forbidden patterns directly to the cardinality of the LOCO code and most importantly to the rule that uncovers the index associated with a LOCO codeword. By doing that, we reveal the secret arithmetic of patterns, and make the design of such constrained codes significantly easier. We give examples illustrating the method via codes based on lexicographic indexing from the literature. We then design optimal (rate-wise) constrained codes for the new two-dimensional magnetic recording (TDMR) technology. Over a practical TDMR model, we show notable performance gains as a result of solely applying the new codes. Moreover, we show how near-optimal constrained codes for TDMR can be designed and used to further reduce complexity and error propagation. All the newly introduced LOCO codes are designed using the proposed general method, and they inherit all the desirable properties in our previously designed LOCO codes. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
17. Hierarchical Hybrid Error Correction for Time-Sensitive Devices at the Edge
- Author
-
Yang, Siyi, Hareedy, Ahmed, Calderbank, Robert, and Dolecek, Lara
- Subjects
FOS: Computer and information sciences ,Information Theory (cs.IT) ,Computer Science - Information Theory - Abstract
Computational storage, known as a solution to significantly reduce the latency by moving data-processing down to the data storage, has received wide attention because of its potential to accelerate data-driven devices at the edge. To meet the insatiable appetite for complicated functionalities tailored for intelligent devices such as autonomous vehicles, properties including heterogeneity, scalability, and flexibility are becoming increasingly important. Based on our prior work on hierarchical erasure coding that enables scalability and flexibility in cloud storage, we develop an efficient decoding algorithm that corrects a mixture of errors and erasures simultaneously. We first extract the basic component code, the so-called extended Cauchy (EC) codes, of the proposed coding solution. We prove that the class of EC codes is strictly larger than that of relevant codes with known explicit decoding algorithms. Motivated by this finding, we then develop an efficient decoding method for the general class of EC codes, based on which we propose the local and global decoding algorithms for the hierarchical codes. Our proposed hybrid error correction not only enables the usage of hierarchical codes in computational storage at the edge, but also applies to any Cauchy-like codes and allows potentially wider applications of the EC codes., 29 pages (single column), 0 figures, to be submitted to IEEE Transactions on Communications
- Published
- 2021
18. MIMO Wireless Communications
- Author
-
Biglieri, Ezio, Calderbank, Robert, Constantinides, Anthony, Goldsmith, Andrea, Paulraj, Arogyaswami, and Poor, H. Vincent
- Published
- 2007
- Full Text
- View/download PDF
19. Robust dimension reduction, fusion frames, and Grassmannian packings
- Author
-
Kutyniok, Gitta, Pezeshki, Ali, Calderbank, Robert, and Liu, Taotao
- Published
- 2009
- Full Text
- View/download PDF
20. Hierarchical Coding for Cloud Storage: Topology-Adaptivity, Scalability, and Flexibility.
- Author
-
Yang, Siyi, Hareedy, Ahmed, Calderbank, Robert, and Dolecek, Lara
- Subjects
SCALABILITY ,BLOCKCHAINS ,DATA warehousing ,CLOUD storage ,INFORMATION storage & retrieval systems ,CHANNEL coding ,DATA protection - Abstract
In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. Sparse fusion frames: existence and construction
- Author
-
Calderbank, Robert, Casazza, Peter G., Heinecke, Andreas, Kutyniok, Gitta, and Pezeshki, Ali
- Published
- 2011
- Full Text
- View/download PDF
22. Efficient and robust compressed sensing using optimized expander graphs
- Author
-
Jafarpour, Sina, Xu, Weiyu, Hassibi, Babak, and Calderbank, Robert
- Subjects
Graphic methods -- Usage ,Sensors -- Methods - Published
- 2009
23. Mitigating Coherent Noise by Balancing Weight-2 Z -Stabilizers.
- Author
-
Hu, Jingzhen, Liang, Qingzhong, Rengaswamy, Narayanan, and Calderbank, Robert
- Subjects
NOISE ,ION traps ,PRODUCT coding ,BLOCK codes ,STOCHASTIC models - Abstract
Physical platforms such as trapped ions suffer from coherent noise that does not follow a simple stochastic model. Stochastic errors in quantum systems occur randomly but coherent errors are more damaging since they can accumulate in a particular direction. We consider coherent noise acting transversally, giving rise to an effective error which is a $Z$ -rotation on each qubit by some angle $\theta $. Rather than address coherent noise through active error correction, we investigate passive mitigation through decoherence free subspaces. In the language of stabilizer codes, we require the noise to preserve the code space, and to act trivially (as the logical identity operator) on the protected information. Thus, we develop necessary and sufficient conditions for all transversal $Z$ -rotations to preserve the code space of a stabilizer code. These conditions require the weight- $2~Z$ -stabilizers to cover all the qubits that are in the support of the $X$ -component of some stabilizer. Furthermore, the weight- $2~Z$ -stabilizers generate a direct product of single-parity-check codes with even block length. By adjusting the sizes of these components, we are able to construct a large family of QECC codes oblivious to coherent noise, one that includes the $[[4L^{2}, 1, 2L]]$ Shor codes. The Shor codes are examples of constant excitation codes, where logical qubits are encoded as a code state that is a sum of physical states indexed by binary vectors with the same weight. Constant excitation codes are oblivious to coherent noise since a transversal $Z$ -rotation acts as a global phase. We prove that a CSS code is oblivious to coherent noise if and only if it is a constant excitation code, and that if the code is error-detecting, then the (constant) weights in different cosets of the $X$ -stabilizers are identical. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
24. Scaling-Translation-Equivariant Networks with Decomposed Convolutional Filters
- Author
-
Zhu, Wei, Qiu, Qiang, Calderbank, Robert, Sapiro, Guillermo, and Cheng, Xiuyuan
- Subjects
FOS: Computer and information sciences ,Computer Science - Machine Learning ,Statistics - Machine Learning ,Machine Learning (stat.ML) ,Machine Learning (cs.LG) - Abstract
Encoding the scale information explicitly into the representation learned by a convolutional neural network (CNN) is beneficial for many computer vision tasks especially when dealing with multiscale inputs. We study, in this paper, a scaling-translation-equivariant (ST-equivariant) CNN with joint convolutions across the space and the scaling group, which is shown to be both sufficient and necessary to achieve equivariance for the regular representation of the scaling-translation group ST . To reduce the model complexity and computational burden, we decompose the convolutional filters under two pre-fixed separable bases and truncate the expansion to low-frequency components. A further benefit of the truncated filter expansion is the improved deformation robustness of the equivariant representation, a property which is theoretically analyzed and empirically verified. Numerical experiments demonstrate that the proposed scaling-translation-equivariant network with decomposed convolutional filters (ScDCFNet) achieves significantly improved performance in multiscale image classification and better interpretability than regular CNNs at a reduced model size.
- Published
- 2019
25. Fake news detection using deep Markov random fields
- Author
-
Nguyen, Minh Duc, do huu, tien, Calderbank, Robert, Deligiannis, Nikolaos, Electronics and Informatics, and Faculty of Engineering
- Subjects
Social media ,Fake News ,Deep learning - Abstract
Deep-learning-based models have been successfully applied to the problem of detecting fake news on social media. While the correlations among news articles have been shown to be effective cues for online news analysis, existing deep-learning-based methods often ignore this information and only consider each news article individually. To overcome this limitation, we develop a graph-theoretic method that inherits the power of deep learning while at the same time utilizing the correlations among the articles. We formulate fake news detection as an inference problem in a Markov random field (MRF) which can be solved by the iterative mean-field algorithm. We then unfold the mean-field algorithm into hidden layers that are composed of common neural network operations. By integrating these hidden layers on top of a deep network, which produces the MRF potentials, we obtain our deep MRF model for fake news detection. Experimental results on well-known datasets show that the proposed model improves upon various state-of-the-art models.
- Published
- 2019
26. Power Spectra of Constrained Codes With Level-Based Signaling: Overcoming Finite-Length Challenges.
- Author
-
Centers, Jessica, Tan, Xinyu, Hareedy, Ahmed, and Calderbank, Robert
- Subjects
POWER spectra ,TELECOMMUNICATION lines ,FLASH memory - Abstract
In various practical systems, certain data patterns are prone to errors if written or transmitted. In magnetic recording and communication over transmission lines, data patterns causing consecutive transitions that are not sufficiently separated are prone to errors. In Flash memory with two levels per cell, data patterns causing high–low–high charge levels on adjacent cells are prone to errors. Constrained codes are used to eliminate error-prone patterns, and they can also achieve other goals. Recently, we introduced efficient binary symmetric lexicographically-ordered constrained (LOCO) codes and asymmetric LOCO (A-LOCO) codes to increase density in magnetic recording systems and lifetime in Flash systems by eliminating the relevant detrimental patterns. Due to their application, LOCO and A-LOCO codes are associated with level-based signaling. Studying the power spectrum of a random signal with certain properties is principal for any storage or transmission system. It reveals important properties such as the average signal power at DC, the bandwidth of the signal, and whether there are discrete power components at certain frequencies. In this paper, we first modify a framework from the literature in order to introduce a method to derive the power spectrum of a sequence of constrained data associated with level-based signaling. We apply our method to infinitely long sequences satisfying symmetric and asymmetric constraints. Next, we show how to generalize the method such that it works for a stream of finite-length codewords as well, thus demonstrating how to overcome the associated finite-length challenges. We use the generalized method to devise closed forms for the spectra of finite-length LOCO and A-LOCO codes from their transition diagrams. Our LOCO and A-LOCO spectral derivations can be performed for any code length and can be extended to other constrained codes. We plot these power spectra, and discuss various important spectral properties for both LOCO and A-LOCO codes. We also briefly discuss an alternative method for deriving the power spectrum and introduce an idea towards reaching the spectra of self-clocked codes. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
27. Obituary: Claude Shannon (1916-2001)
- Author
-
Calderbank, Robert and Sloane, Neil J. A.
- Published
- 2001
28. CHIRRUP: a practical algorithm for unsourced multiple access.
- Author
-
Calderbank, Robert and Thompson, Andrew
- Subjects
- *
REED-Muller codes , *ALGORITHMS , *MACHINE-to-machine communications , *AD hoc computer networks , *SCIENCE conferences , *SYSTEMS theory , *INTERNET of things - Abstract
Unsourced multiple access abstracts grantless simultaneous communication of a large number of devices (messages) each of which transmits (is transmitted) infrequently. It provides a model for machine-to-machine communication in the Internet of Things, including the special case of radio-frequency identification, as well as neighbour discovery in ad hoc wireless networks. This paper presents a fast algorithm for unsourced multiple access that scales to |${\mathscr{C}}=2^{100}$| (active or non-active) devices (arbitrary |$100$| bit messages). The primary building block is multiuser detection of binary chirps, which are simply codewords in the second-order Reed–Muller code. The chirp detection algorithm originally presented by Howard et al. (2008, 42nd Annual Conference on Information Sciences and Systems) is enhanced and integrated into a peeling decoder designed for a patching and slotting framework. In terms of both energy per bit and number of active devices (number of transmitted messages), the proposed algorithm is within a factor of |$2$| of state-of-the-art approaches. A significant advantage of our algorithm is its computational efficiency. We prove that the worst-case complexity of the basic chirp reconstruction algorithm is |${\mathscr{O}}[nK(\log _2^2 n + K)]$| , where |$n$| is the codeword length and |$K$| is the number of active users. Crucially, the complexity is sublinear in |${\mathscr{C}}$| , which makes the reconstruction computationally feasible—a claim we support by reporting computing times for our algorithm. Our performance and computing time results represent a benchmark against which other practical algorithms can be measured. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
29. Non-Binary Constrained Codes for Two-Dimensional Magnetic Recording.
- Author
-
Dabak, Beyza, Hareedy, Ahmed, and Calderbank, Robert
- Subjects
TWO-dimensional bar codes ,CIPHERS ,DATA protection ,RELIABILITY in engineering ,MAGNETIC recording heads ,DATA warehousing - Abstract
The two-dimensional magnetic recording (TDMR) technology promises storage densities of 10 Tbits/in2. However, when tracks are squeezed together, a bit stored in the two-dimensional (TD) grid suffers inter-symbol interference (ISI) from adjacent bits in the same track and inter-track interference (ITI) from nearby bits in the adjacent tracks. A bit is highly likely to be read incorrectly if it is isolated in the middle of a $3 \times 3$ square, surrounded by its complements, horizontally and vertically. We improve the reliability of TDMR systems by designing TD constrained codes that prevent these square isolation patterns. We exploit the way TD read heads operate to design our codes, and we focus on TD read heads that collect signals from three adjacent tracks. We represent the two-dimensional square isolation constraint as a one-dimensional constraint on an alphabet of eight non-binary symbols. We use this new representation to construct a non-binary lexicographically-ordered constrained code where one third of the input information bits are unconstrained. Our TD constraint codes are capacity-achieving, and the data protection is achieved with redundancy less than 3% and at modest complexity. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
30. Kerdock Codes Determine Unitary 2-Designs.
- Author
-
Can, Trung, Rengaswamy, Narayanan, Calderbank, Robert, and Pfister, Henry D.
- Subjects
MAXIMAL subgroups ,PAULI matrices ,CYCLIC codes ,AUTOMORPHISM groups ,QUANTUM states ,GRAY codes ,CLIFFORD algebras - Abstract
The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length $N = 2^{m}$ over $\mathbb {Z}_{4}$. We show that exponentiating these $\mathbb {Z}_{4}$ -valued codewords by $i \triangleq \sqrt {-1}$ produces stabilizer states, that are quantum states obtained using only Clifford unitaries. These states are also the common eigenvectors of commuting Hermitian matrices forming maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the derivation of the classical weight distribution of Kerdock codes. Next, we organize the stabilizer states to form $N+1$ mutually unbiased bases and prove that automorphisms of the Kerdock code permute their corresponding MCS, thereby forming a subgroup of the Clifford group. When represented as symplectic matrices, this subgroup is isomorphic to the projective special linear group PSL($2,N$). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is Pauli mixing and hence forms a unitary 2-design. The Kerdock design described here was originally discovered by Cleve et al. (2016), but the connection to classical codes is new which simplifies its description and translation to circuits significantly. Sampling from the design is straightforward, the translation to circuits uses only Clifford gates, and the process does not require ancillary qubits. Finally, we also develop algorithms for optimizing the synthesis of unitary 2-designs on encoded qubits, i.e., to construct logical unitary 2-designs. Software implementations are available at https://github.com/nrenga/symplectic-arxiv18a , which we use to provide empirical gate complexities for up to 16 qubits. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
31. Minimizing the Number of Detrimental Objects in Multi-Dimensional Graph-Based Codes.
- Author
-
Hareedy, Ahmed, Kuditipudi, Rohith, and Calderbank, Robert
- Subjects
DATA warehousing ,CIPHERS ,LOW density parity check codes ,ITERATIVE decoding ,FLASH memory - Abstract
The increasing demand for access to data has led to dramatic increases in data storage densities, and as densities increase, new sources of error appear. Multi-dimensional (MD) graph-based codes are capable of mitigating error sources like interference and channel non-uniformity in dense storage devices. A recent innovation improves the performance of MD spatially-coupled codes that are based on circulants by carefully relocating some circulants to minimize the number of short cycles. However, cycles become more detrimental when they combine together to form more advanced objects, e.g., absorbing sets, including low-weight codewords. In this paper, we show how MD relocations can be exploited to minimize the number of detrimental objects in the graph of an MD code. Moreover, we demonstrate the savings in the number of relocation arrangements earned by focusing on objects rather than their constituent cycles. Our technique is applicable to a wide variety of one-dimensional (OD) codes. Simulation results demonstrate significant lifetime gains achieved by the proposed MD codes on an industry-recommended model for Flash systems, and signal-to-noise ratio gains on an industry-recommended model for magnetic recording systems, both with respect to OD codes with similar parameters. The second order analysis of MD relocations relies on conditions and options for an object, called a pattern, to form a bigger cycle after MD relocations, which are discussed in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
32. Use of a Digital M-CHAT-R/F to Improve Quality of Screening for Autism
- Author
-
Campbell, Kathleen, Carpenter, Kimberly L.H., Espinosa, Steven, Hashemi, Jordan, Qiu, Qiang, Tepper, Mariano, Calderbank, Robert, Sapiro, Guillermo, Egger, Helen L., Baker, Jeffrey P., and Dawson, Geraldine
- Subjects
Male ,Autism Spectrum Disorder ,Incidence ,Age Factors ,Infant ,Quality Improvement ,Risk Assessment ,Severity of Illness Index ,Article ,Checklist ,Early Diagnosis ,Child, Preschool ,Electronic Health Records ,Humans ,Mass Screening ,Female ,Follow-Up Studies - Abstract
To assess changes in quality of care for children at risk for autism spectrum disorders (ASD) due to process improvement and implementation of a digital screening form.The process of screening for ASD was studied in an academic primary care pediatrics clinic before and after implementation of a digital version of the Modified Checklist for Autism in Toddlers - Revised with Follow-up with automated risk assessment. Quality metrics included accuracy of documentation of screening results and appropriate action for positive screens (secondary screening or referral). Participating physicians completed pre- and postintervention surveys to measure changes in attitudes toward feasibility and value of screening for ASD. Evidence of change was evaluated with statistical process control charts and χAccurate documentation in the electronic health record of screening results increased from 54% to 92% (38% increase, 95% CI 14%-64%) and appropriate action for children screening positive increased from 25% to 85% (60% increase, 95% CI 35%-85%). A total of 90% of participating physicians agreed that the transition to a digital screening form improved their clinical assessment of autism risk.Implementation of a tablet-based digital version of the Modified Checklist for Autism in Toddlers - Revised with Follow-up led to improved quality of care for children at risk for ASD and increased acceptability of screening for ASD. Continued efforts towards improving the process of screening for ASD could facilitate rapid, early diagnosis of ASD and advance the accuracy of studies of the impact of screening.
- Published
- 2017
33. Correcting Two Deletions and Insertions in Racetrack Memory
- Author
-
Vahid, Alireza, Mappouras, Georgios, Sorin, Daniel J., and Calderbank, Robert
- Subjects
FOS: Computer and information sciences ,Information Theory (cs.IT) ,Computer Science - Information Theory - Abstract
Racetrack memory is a non-volatile memory engineered to provide both high density and low latency, that is subject to synchronization or shift errors. This paper describes a fast coding solution, in which delimiter bits assist in identifying the type of shift error, and easily implementable graph-based codes are used to correct the error, once identified. A code that is able to detect and correct double shift errors is described in detail., Technical report 2017
- Published
- 2017
34. Classification Scheme for Binary Data with Extensions
- Author
-
Molitor, Denali, Needell, Deanna, Nelson, Aaron, Saab, Rayan, Salanevich, Palina, Boche, Holger, Caire, Giuseppe, Calderbank, Robert, Kutyniok, Gitta, Mathar, Rudolf, and Petersen, Philipp
- Subjects
Computer science ,Computation ,Applied Mathematics ,Classification scheme ,computer.software_genre ,Hierarchical database model ,Variety (cybernetics) ,Data model ,Simple (abstract algebra) ,Binary data ,Taverne ,Data mining ,computer ,Test data - Abstract
In this chapter, we present a simple classification scheme that utilizes only 1-bit measurements of the training and testing data. Our method is intended to be efficient in terms of computation and storage while also allowing for a rigorous mathematical analysis. After providing some motivation, we present our method and analyze its performance for a simple data model. We also discuss extensions of the method to the hierarchical data setting, and include some further implementation considerations. Experimental evidence provided in this chapter demonstrates that our methods yield accurate classification on a variety of synthetic and real data.
- Published
- 2019
35. LOCO Codes: Lexicographically-Ordered Constrained Codes.
- Author
-
Hareedy, Ahmed and Calderbank, Robert
- Subjects
- *
CIRCUIT complexity , *CIPHERS , *OPTICAL devices , *MAGNETICS , *FLASH memory , *BINARY codes - Abstract
Line codes make it possible to mitigate interference, to prevent short pulses, and to generate streams of bipolar signals with no direct-current (DC) power content through balancing. They find application in magnetic recording (MR) devices, in Flash devices, in optical recording devices, and in some computer standards. This paper introduces a new family of fixed-length, binary constrained codes, named lexicographically-ordered constrained codes (LOCO codes), for bipolar non-return-to-zero signaling. LOCO codes are capacity-achieving, the lexicographic indexing enables simple, practical encoding and decoding, and this simplicity is demonstrated through analysis of circuit complexity. LOCO codes are easy to balance, and their inherent symmetry minimizes the rate loss with respect to unbalanced codes having the same constraints. Furthermore, LOCO codes that forbid certain patterns can be used to alleviate inter-symbol interference in MR systems and inter-cell interference in Flash systems. Numerical results demonstrate a gain of up to 10% in rate achieved by LOCO codes with respect to other practical constrained codes, including run-length-limited codes, designed for the same purpose. Simulation results suggest that it is possible to achieve a channel density gain of about 20% in MR systems by using a LOCO code to encode only the parity bits, limiting the rate loss, of a low-density parity-check code before writing. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
36. GraphConnect: A Regularization Framework for Neural Networks
- Author
-
Huang, Jiaji, Qiu, Qiang, Calderbank, Robert, and Sapiro, Guillermo
- Subjects
FOS: Computer and information sciences ,Computer Science - Learning ,Computer Vision and Pattern Recognition (cs.CV) ,Computer Science - Computer Vision and Pattern Recognition ,Computer Science - Neural and Evolutionary Computing ,Neural and Evolutionary Computing (cs.NE) ,Machine Learning (cs.LG) - Abstract
Deep neural networks have proved very successful in domains where large training sets are available, but when the number of training samples is small, their performance suffers from overfitting. Prior methods of reducing overfitting such as weight decay, Dropout and DropConnect are data-independent. This paper proposes a new method, GraphConnect, that is data-dependent, and is motivated by the observation that data of interest lie close to a manifold. The new method encourages the relationships between the learned decisions to resemble a graph representing the manifold structure. Essentially GraphConnect is designed to learn attributes that are present in data samples in contrast to weight decay, Dropout and DropConnect which are simply designed to make it more difficult to fit to random error or noise. Empirical Rademacher complexity is used to connect the generalization error of the neural network to spectral properties of the graph learned from the input data. This framework is used to show that GraphConnect is superior to weight decay. Experimental results on several benchmark datasets validate the theoretical analysis, and show that when the number of training samples is small, GraphConnect is able to significantly improve performance over weight decay., Theorems need more validation
- Published
- 2015
37. Geometric Matrix Completion With Deep Conditional Random Fields.
- Author
-
Nguyen, Duc Minh, Calderbank, Robert, and Deligiannis, Nikos
- Subjects
- *
RANDOM fields , *RECOMMENDER systems , *MARKOV random fields , *MATRICES (Mathematics) , *GEOMETRIC modeling , *FORECASTING , *RANDOM matrices , *REPRESENTATIONS of graphs - Abstract
The problem of completing high-dimensional matrices from a limited set of observations arises in many big data applications, especially recommender systems. The existing matrix completion models generally follow either a memory- or a model-based approach, whereas geometric matrix completion (GMC) models combine the best from both approaches. Existing deep-learning-based geometric models yield good performance, but, in order to operate, they require a fixed structure graph capturing the relationships among the users and items. This graph is typically constructed by evaluating a pre-defined similarity metric on the available observations or by using side information, e.g., user profiles. In contrast, Markov-random-fields-based models do not require a fixed structure graph but rely on handcrafted features to make predictions. When no side information is available and the number of available observations becomes very low, existing solutions are pushed to their limits. In this article, we propose a GMC approach that addresses these challenges. We consider matrix completion as a structured prediction problem in a conditional random field (CRF), which is characterized by a maximum a posteriori (MAP) inference, and we propose a deep model that predicts the missing entries by solving the MAP inference problem. The proposed model simultaneously learns the similarities among matrix entries, computes the CRF potentials, and solves the inference problem. Its training is performed in an end-to-end manner, with a method to supervise the learning of entry similarities. Comprehensive experiments demonstrate the superior performance of the proposed model compared to various state-of-the-art models on popular benchmark data sets and underline its superior capacity to deal with highly incomplete matrices. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
38. Computational Security Subject to Source Constraints, Guesswork and Inscrutability
- Author
-
Beirami, Ahmad, Calderbank, Robert, Duffy, Ken, and Medard, Muriel
- Subjects
Hamilton Institute - Abstract
Guesswork forms the mathematical framework for quantifying computational security subject to brute-force determination by query. In this paper, we consider guesswork subject to a per-symbol Shannon entropy budget. We introduce inscrutability rate to quantify the asymptotic difficulty of guessing U out of V secret strings drawn from the string-source and prove that the inscrutability rate of any string-source supported on a finite alphabet X, if it exists, lies between the per-symbol Shannon entropy constraint and log |X|. We show that for a stationary string-source, the inscrutability rate of guessing any fraction (1 - ϵ) of the V strings for any fixed ϵ > 0, as V grows, approaches the per-symbol Shannon entropy constraint (which is equal to the Shannon entropy rate for the stationary string-source). This corresponds to the minimum inscrutability rate among all string-sources with the same per-symbol Shannon entropy. We further prove that the inscrutability rate of any finite-order Markov string-source with hidden statistics remains the same as the unhidden case, i.e., the asymptotic value of hiding the statistics per each symbol is vanishing. On the other hand, we show that there exists a string-source that achieves the upper limit on the inscrutability rate, i.e., log |X|, under the same Shannon entropy budget.
- Published
- 2015
39. A Characterization of Guesswork on Swiftly Tilting Curves.
- Author
-
Beirami, Ahmad, Calderbank, Robert, Christiansen, Mark M., Duffy, Ken R., and Medard, Muriel
- Subjects
- *
MAXIMUM likelihood decoding , *SEQUENTIAL decoding , *COMPUTATIONAL complexity , *CHANNEL coding , *DECODING algorithms - Abstract
Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
40. Multi-Scale Spectrum Sensing in Dense Multi-Cell Cognitive Networks.
- Author
-
Michelusi, Nicolo, Nokleby, Matthew, Mitra, Urbashi, and Calderbank, Robert
- Subjects
COGNITIVE radio ,RADIO transmitter-receivers ,5G networks ,WIRELESS sensor networks ,SPECTRUM analysis - Abstract
Multi-scale spectrum sensing is proposed to overcome the cost of full network state information on the spectrum occupancy of primary users (PUs) in dense multi-cell cognitive networks. Secondary users (SUs) estimate the local spectrum occupancies and aggregate them hierarchically to estimate spectrum occupancy at multiple spatial scales. Thus, SUs obtain fine-grained estimates of spectrum occupancies of nearby cells, more relevant to scheduling tasks, and coarse-grained estimates of those of distant cells. An agglomerative clustering algorithm is proposed to design a cost-effective aggregation tree, matched to the structure of interference, robust to local estimation errors, and delays. Given these multi-scale estimates, the SU traffic is adapted in a decentralized fashion in each cell, to optimize the trade-off among SU cell throughput, interference caused to PUs, and mutual SU interference. Numerical evaluations demonstrate a small degradation in SU cell throughput (up to 15% for a 0 dB interference-to-noise ratio experienced at PUs) compared to a scheme with full network state information, using only one-third of the cost incurred in the exchange of spectrum estimates. The proposed interference-matched design is shown to significantly outperform a random tree design, by providing more relevant information for network control, and a state-of-the-art consensus-based algorithm, which does not leverage the spatio-temporal structure of interference across the network. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
41. Throughput Region of Spatially Correlated Interference Packet Networks.
- Author
-
Vahid, Alireza and Calderbank, Robert
- Subjects
- *
MIMO systems , *TRANSMITTERS (Communication) , *INTERFERENCE (Telecommunication) , *SIGNAL processing , *WIRELESS sensor networks , *DATA transmission systems - Abstract
In multi-user wireless packet networks, interference, typically modeled as packet collision, is the throughput bottleneck. Users become aware of the interference pattern via feedback and use this information for contention resolution and packet retransmission. Conventional random access protocols interrupt communication to resolve contention, which reduces network throughput and increases latency and power consumption. In this paper, we take a different approach, and we develop opportunistic random access protocols rather than pursuing conventional methods. We allow wireless nodes to communicate without interruption and to observe the interference pattern. We then use this interference pattern knowledge and channel statistics to counter the negative impact of interference. We prove the optimality of our protocols using an extremal rank-ratio inequality. An important part of our contributions is the integration of spatial correlation in our assumptions and results. We identify spatial correlation regimes in which inherently outdated feedback becomes as good as idealized instantaneous feedback and correlation regimes in which feedback does not provide any throughput gain. To better illustrate the results, and as an intermediate step, we characterize the capacity region of finite-field spatially correlated interference channels with delayed channel state information at the transmitters. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
42. Extending Flash Lifetime in Embedded Processors by Expanding Analog Choice.
- Author
-
Mappouras, Georgios, Vahid, Alireza, Calderbank, Robert, and Sorin, Daniel J.
- Subjects
FLASH memory ,EMBEDDED computer systems ,MICROPROCESSORS ,ANALOG data ,PHASE distortion (Electronics) ,COMPUTER architecture - Abstract
We extend the lifetime of Flash memory in embedded processors by exploiting the fact that data from sensors is inherently analog. Prior work in the computer architecture community has assumed that all data is digital and has overlooked the opportunities available when working with analog data, such as the data recorded by sensors. In this paper, we introduce redundancy into the quantization of sensor data in order to provide several alternative representations. Notably, we tradeoff distortion—the difference between the sensed analog value and the digital quantization of that value—to improve lifetime. Our simulations show that when combining rate, distortion, and lifetime tradeoffs we can extend Flash lifetime at a far smaller capacity cost compared to prior work. More specifically the simulated system shows that it is possible to achieve up to $2.75 \times$ less capacity cost compared to redundant Flash memory and $1.29 \times$ less capacity cost compared to the state of the art coding schemes. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
43. Space-time processing for broadband wireless access
- Author
-
Al-Dhahir, Naofal, Fragouli, Christina, Stamoulis, Anastasios, Younis, Waleed, and Calderbank, Robert
- Subjects
Broadband Internet ,Broadband transmission -- Research - Published
- 2002
44. A fourth-generation MIMO-OFDM broadbad wireless system: design, performance, and field trial results
- Author
-
Sampath, Hemanth, Talwar, Shilpa, Tellado, Jose, Erceg, Vinko, and Calderbank, Robert
- Subjects
Cable television/data services ,Online services ,Broadband Internet ,Online services -- Equipment and supplies ,Broadband transmission -- Equipment and supplies - Published
- 2002
45. Discrimination on the Grassmann Manifold: Fundamental Limits of Subspace Classifiers
- Author
-
Nokleby, Matthew, Rodrigues, Miguel, and Calderbank, Robert
- Subjects
FOS: Computer and information sciences ,ComputingMethodologies_PATTERNRECOGNITION ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Computer Science::Information Theory - Abstract
We present fundamental limits on the reliable classification of linear and affine subspaces from noisy, linear features. Drawing an analogy between discrimination among subspaces and communication over vector wireless channels, we propose two Shannon-inspired measures to characterize asymptotic classifier performance. First, we define the classification capacity, which characterizes necessary and sufficient conditions for the misclassification probability to vanish as the signal dimension, the number of features, and the number of subspaces to be discerned all approach infinity. Second, we define the diversity-discrimination tradeoff which, by analogy with the diversity-multiplexing tradeoff of fading vector channels, characterizes relationships between the number of discernible subspaces and the misclassification probability as the noise power approaches zero. We derive upper and lower bounds on these measures which are tight in many regimes. Numerical results, including a face recognition application, validate the results in practice., 19 pages, 4 figures. Revised submission to IEEE Transactions on Information Theory
- Published
- 2014
46. Fusion Frames: Existence and Construction
- Author
-
Calderbank, Robert, Casazza, Peter G., Heinecke, Andreas, Kutyniok, Gitta, and Pezeshki, Ali
- Subjects
Mathematics - Functional Analysis ,Physics::Plasma Physics ,94A12 ,FOS: Mathematics ,Representation Theory (math.RT) ,Mathematics - Representation Theory ,Functional Analysis (math.FA) - Abstract
Fusion frame theory is an emerging mathematical theory that provides a natural framework for performing hierarchical data processing. A fusion frame is a frame-like collection of subspaces in a Hilbert space, thereby generalizing the concept of a frame for signal representation. In this paper, we study the existence and construction of fusion frames. We first present a complete characterization of a special class of fusion frames, called Parseval fusion frames. The value of Parseval fusion frames is that the inverse fusion frame operator is equal to the identity and therefore signal reconstruction can be performed with minimal complexity. We then introduce two general methods -- the spatial complement and the Naimark complement -- for constructing a new fusion frame from a given fusion frame. We then establish existence conditions for fusion frames with desired properties. In particular, we address the following question: Given $M, N, m \in \NN$ and $\{\lambda_j\}_{j=1}^M$, does there exist a fusion frame in $\RR^M$ with $N$ subspaces of dimension $m$ for which $\{\lambda_j\}_{j=1}^M$ are the eigenvalues of the associated fusion frame operator? We address this problem by providing an algorithm which computes such a fusion frame for almost any collection of parameters $M, N, m \in \NN$ and $\{\lambda_j\}_{j=1}^M$. Moreover, we show how this procedure can be applied, if subspaces are to be added to a given fusion frame to force it to become Parseval., Comment: 24 pages
- Published
- 2009
47. A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees
- Author
-
Calderbank, Robert, Howard, Stephen, and Jafarpour, Sina
- Subjects
FOS: Computer and information sciences ,Statistics::Machine Learning ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Physics::Space Physics ,Physics::Classical Physics - Abstract
Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Cand\`{e}s and Tao showed that sparse reconstruction is possible if the sensing matrix acts as a near isometry on all $\boldsymbol{k}$-sparse signals. This property holds with overwhelming probability if the entries of the matrix are generated by an iid Gaussian or Bernoulli process. There has been significant recent interest in an alternative signal processing framework; exploiting deterministic sensing matrices that with overwhelming probability act as a near isometry on $\boldsymbol{k}$-sparse vectors with uniformly random support, a geometric condition that is called the Statistical Restricted Isometry Property or StRIP. This paper considers a family of deterministic sensing matrices satisfying the StRIP that are based on \srm codes (binary chirps) and a $\boldsymbol{k}$-sparse reconstruction algorithm with sublinear complexity. In the presence of stochastic noise in the data domain, this paper derives bounds on the $\boldsymbol{\ell_2}$ accuracy of approximation in terms of the $\boldsymbol{\ell_2}$ norm of the measurement noise and the accuracy of the best $\boldsymbol{k}$-sparse approximation, also measured in the $\boldsymbol{\ell_2}$ norm. This type of $\boldsymbol{\ell_2 /\ell_2}$ bound is tighter than the standard $\boldsymbol{\ell_2 /\ell_1}$ or $\boldsymbol{\ell_1/ \ell_1}$ bounds.
- Published
- 2008
48. A general framework for reconstruction and classification from compressive measurements with side information.
- Author
-
Wang, Liming, Renna, Francesco, Yuan, Xin, Rodrigues, Miguel, Calderbank, Robert, and Carin, Lawrence
- Published
- 2016
- Full Text
- View/download PDF
49. Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels.
- Author
-
Kumar, Santhosh, Calderbank, Robert, and Pfister, Henry D.
- Published
- 2016
- Full Text
- View/download PDF
50. Writing without Disturb on Phase Change Memories by Integrating Coding and Layout Design.
- Author
-
Eslami, Ali, Velasco, Alfredo, Vahid, Alireza, Mappouras, Georgios, Calderbank, Robert, and Sorin, Daniel J.
- Published
- 2015
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.