Showing 1–50 of 51 results for author: Jalali, S

Untrained Neural Nets for Snapshot Compressive Imaging: Theory and Algorithms

Authors: Mengyu Zhao, Xi Chen, Xin Yuan, Shirin Jalali

Abstract: Snapshot compressive imaging (SCI) recovers high-dimensional (3D) data cubes from a single 2D measurement, enabling diverse applications like video and hyperspectral imaging to go beyond standard techniques in terms of acquisition speed and efficiency. In this paper, we focus on SCI recovery algorithms that employ untrained neural networks (UNNs), such as deep image prior (DIP), to model source st… ▽ More Snapshot compressive imaging (SCI) recovers high-dimensional (3D) data cubes from a single 2D measurement, enabling diverse applications like video and hyperspectral imaging to go beyond standard techniques in terms of acquisition speed and efficiency. In this paper, we focus on SCI recovery algorithms that employ untrained neural networks (UNNs), such as deep image prior (DIP), to model source structure. Such UNN-based methods are appealing as they have the potential of avoiding the computationally intensive retraining required for different source models and different measurement scenarios. We first develop a theoretical framework for characterizing the performance of such UNN-based methods. The theoretical framework, on the one hand, enables us to optimize the parameters of data-modulating masks, and on the other hand, provides a fundamental connection between the number of data frames that can be recovered from a single measurement to the parameters of the untrained NN. We also employ the recently proposed bagged-deep-image-prior (bagged-DIP) idea to develop SCI Bagged Deep Video Prior (SCI-BDVP) algorithms that address the common challenges faced by standard UNN solutions. Our experimental results show that in video SCI our proposed solution achieves state-of-the-art among UNN methods, and in the case of noisy measurements, it even outperforms supervised solutions. △ Less

Submitted 5 June, 2024; originally announced June 2024.

About: "Float stacked graphene PMMA laminate"

Authors: Anirban Kundu, Won Kyung Seong, S. Kamal Jalali, Nicola M. Pugno, Rodney S. Ruoff

Abstract: We report the scientific and technical queries regarding the article reported by Kim et al.1 on the mechanical properties of graphene-poly(methyl methacrylate) (PMMA) composites. Our analysis finds that the current experimental data is insufficient to fully support the conclusions presented in the article. We suggest the enhancement in Youngs modulus and strength of the graphene-PMMA laminates (GP… ▽ More We report the scientific and technical queries regarding the article reported by Kim et al.1 on the mechanical properties of graphene-poly(methyl methacrylate) (PMMA) composites. Our analysis finds that the current experimental data is insufficient to fully support the conclusions presented in the article. We suggest the enhancement in Youngs modulus and strength of the graphene-PMMA laminates (GPL) samples are mainly due to the heat treatment of the polymer rather than the incorporation of graphene. The Raman spectroscopy data (as per our analysis) for the GPL samples indicates that large cracks and defects were introduced during the hot rolling process used to fabricate the graphene-PMMA composite. We believe that the queries will aid the audience in better understanding the mechanical response of graphene-PMMA composites. △ Less

Submitted 27 May, 2024; v1 submitted 20 May, 2024; originally announced May 2024.

Comments: 14 Pages, 4 Figures

LiMAML: Personalization of Deep Recommender Models via Meta Learning

Authors: Ruofan Wang, Prakruthi Prabhakar, Gaurav Srivastava, Tianqi Wang, Zeinab S. Jalali, Varun Bharill, Yunbo Ouyang, Aastha Nigam, Divya Venugopalan, Aman Gupta, Fedor Borisyuk, Sathiya Keerthi, Ajith Muralidharan

Abstract: In the realm of recommender systems, the ubiquitous adoption of deep neural networks has emerged as a dominant paradigm for modeling diverse business objectives. As user bases continue to expand, the necessity of personalization and frequent model updates have assumed paramount significance to ensure the delivery of relevant and refreshed experiences to a diverse array of members. In this work, we… ▽ More In the realm of recommender systems, the ubiquitous adoption of deep neural networks has emerged as a dominant paradigm for modeling diverse business objectives. As user bases continue to expand, the necessity of personalization and frequent model updates have assumed paramount significance to ensure the delivery of relevant and refreshed experiences to a diverse array of members. In this work, we introduce an innovative meta-learning solution tailored to the personalization of models for individual members and other entities, coupled with the frequent updates based on the latest user interaction signals. Specifically, we leverage the Model-Agnostic Meta Learning (MAML) algorithm to adapt per-task sub-networks using recent user interaction data. Given the near infeasibility of productionizing original MAML-based models in online recommendation systems, we propose an efficient strategy to operationalize meta-learned sub-networks in production, which involves transforming them into fixed-sized vectors, termed meta embeddings, thereby enabling the seamless deployment of models with hundreds of billions of parameters for online serving. Through extensive experimentation on production data drawn from various applications at LinkedIn, we demonstrate that the proposed solution consistently outperforms the baseline models of those applications, including strong baselines such as using wide-and-deep ID based personalization approach. Our approach has enabled the deployment of a range of highly personalized AI models across diverse LinkedIn applications, leading to substantial improvements in business metrics as well as refreshed experience for our members. △ Less

Submitted 23 February, 2024; originally announced March 2024.

Bagged Deep Image Prior for Recovering Images in the Presence of Speckle Noise

Authors: Xi Chen, Zhewen Hou, Christopher A. Metzler, Arian Maleki, Shirin Jalali

Abstract: We investigate both the theoretical and algorithmic aspects of likelihood-based methods for recovering a complex-valued signal from multiple sets of measurements, referred to as looks, affected by speckle (multiplicative) noise. Our theoretical contributions include establishing the first existing theoretical upper bound on the Mean Squared Error (MSE) of the maximum likelihood estimator under the… ▽ More We investigate both the theoretical and algorithmic aspects of likelihood-based methods for recovering a complex-valued signal from multiple sets of measurements, referred to as looks, affected by speckle (multiplicative) noise. Our theoretical contributions include establishing the first existing theoretical upper bound on the Mean Squared Error (MSE) of the maximum likelihood estimator under the deep image prior hypothesis. Our theoretical results capture the dependence of MSE upon the number of parameters in the deep image prior, the number of looks, the signal dimension, and the number of measurements per look. On the algorithmic side, we introduce the concept of bagged Deep Image Priors (Bagged-DIP) and integrate them with projected gradient descent. Furthermore, we show how employing Newton-Schulz algorithm for calculating matrix inverses within the iterations of PGD reduces the computational complexity of the algorithm. We will show that this method achieves the state-of-the-art performance. △ Less

Submitted 23 February, 2024; originally announced February 2024.

Theoretical Analysis of Binary Masks in Snapshot Compressive Imaging Systems

Authors: Mengyu Zhao, Shirin Jalali

Abstract: Snapshot compressive imaging (SCI) systems have gained significant attention in recent years. While previous theoretical studies have primarily focused on the performance analysis of Gaussian masks, practical SCI systems often employ binary-valued masks. Furthermore, recent research has demonstrated that optimized binary masks can significantly enhance system performance. In this paper, we present… ▽ More Snapshot compressive imaging (SCI) systems have gained significant attention in recent years. While previous theoretical studies have primarily focused on the performance analysis of Gaussian masks, practical SCI systems often employ binary-valued masks. Furthermore, recent research has demonstrated that optimized binary masks can significantly enhance system performance. In this paper, we present a comprehensive theoretical characterization of binary masks and their impact on SCI system performance. Initially, we investigate the scenario where the masks are binary and independently identically distributed (iid), revealing a noteworthy finding that aligns with prior numerical results. Specifically, we show that the optimal probability of non-zero elements in the masks is smaller than 0.5. This result provides valuable insights into the design and optimization of binary masks for SCI systems, facilitating further advancements in the field. Additionally, we extend our analysis to characterize the performance of SCI systems where the mask entries are not independent but are generated based on a stationary first-order Markov process. Overall, our theoretical framework offers a comprehensive understanding of the performance implications associated with binary masks in SCI systems. △ Less

Submitted 15 July, 2023; originally announced July 2023.

Structural changes induced by electric currents in a single crystal of Pr$_2$CuO$_4$

Authors: Susmita Roy, Feng Ye, Zachary Morgan, Syed I. A. Jalali, Yu Zhang, Gang Cao, Nobu-Hisa Kaneko, Martin Greven, Rishi Raj, Dmitry Reznik

Abstract: We demonstrate a novel approach to the structural and electronic property modification of perovskites, focusing on Pr$_2$CuO$_4$, an undoped parent compound of a class of electron-doped copper-oxide superconductors. Currents were passed parallel or perpendicular to the copper-oxygen layers with the voltage ramped up until a rapid drop in the resistivity was achieved, a process referred to as "flas… ▽ More We demonstrate a novel approach to the structural and electronic property modification of perovskites, focusing on Pr$_2$CuO$_4$, an undoped parent compound of a class of electron-doped copper-oxide superconductors. Currents were passed parallel or perpendicular to the copper-oxygen layers with the voltage ramped up until a rapid drop in the resistivity was achieved, a process referred to as "flash". The current was then further increased tenfold in current-control mode. This state was quenched by immersion into liquid nitrogen. Flash can drive many compounds into different atomic structures with new properties, whereas the quench freezes them into a long-lived state. Single-crystal neutron diffraction of as-grown and modified Pr$_2$CuO$_4$ revealed a $\sqrt{10}$x$\sqrt{10}$ superlattice due to oxygen-vacancy order. The diffraction peak intensities of the superlattice of the modified sample were significantly enhanced relative to the pristine sample. Raman-active phonons in the modified sample were considerably sharper. Measurements of electrical resistivity, magnetization and two-magnon Raman scattering indicate that the modification affected only the Pr-O layers, but not the Cu-O planes. These results point to enhanced oxygen-vacancy order in the modified samples well beyond what can be achieved without passing electrical current. Our work opens a new avenue toward electric field/quench control of structure and properties of layered perovskite oxides. △ Less

Submitted 7 September, 2023; v1 submitted 8 February, 2023; originally announced February 2023.

Journal ref: Phys. Rev. Materials 7, 083803 (2023)

Social Stratification in Networks: Insights from Co-Authorship Networks

Authors: Zeinab S. Jalali, Josh Introne, Sucheta Soundarajan

Abstract: It has been observed that real-world social networks often exhibit stratification along economic or other lines, with consequences for class mobility and access to opportunities. With the rise in human interaction data and extensive use of online social networks, the structure of social networks (representing connections between individuals) can be used for measuring stratification. However, altho… ▽ More It has been observed that real-world social networks often exhibit stratification along economic or other lines, with consequences for class mobility and access to opportunities. With the rise in human interaction data and extensive use of online social networks, the structure of social networks (representing connections between individuals) can be used for measuring stratification. However, although stratification has been studied extensively in the social sciences, there is no single, generally applicable metric for measuring the level of stratification in a network. In this work, we first propose the novel Stratification Assortativity (StA) metric, which measures the extent to which a network is stratified into different tiers. Then, we use the \texttt{StA} metric to perform an in-depth analysis of the stratification of five co-authorship networks. We examine the evolution of these networks over 50 years and show that these fields demonstrate an increasing level of stratification over time, and, correspondingly, the trajectory of a researcher's career is increasingly correlated with her entry point into the network. △ Less

Submitted 3 December, 2022; originally announced December 2022.

Comments: 21 pages

Journal ref: Royal Society Interface, 2022

Tides Need STEMMED: A Locally Operating Spatio-Temporal Mutually Exciting Point Process with Dynamic Network for Improving Opioid Overdose Death Prediction

Authors: Che-Yi Liao, Gian-Gabriel Garcia, Kamran Paynabar, Zheng Dong, Yao Xie, Mohammad S. Jalali

Abstract: We develop a Spatio-TEMporal Mutually Exciting point process with Dynamic network (STEMMED), i.e., a point process network wherein each node models a unique community-drug event stream with a dynamic mutually-exciting structure, accounting for influences from other nodes. We show that STEMMED can be decomposed node-by-node, suggesting a tractable distributed learning procedure. Simulation shows th… ▽ More We develop a Spatio-TEMporal Mutually Exciting point process with Dynamic network (STEMMED), i.e., a point process network wherein each node models a unique community-drug event stream with a dynamic mutually-exciting structure, accounting for influences from other nodes. We show that STEMMED can be decomposed node-by-node, suggesting a tractable distributed learning procedure. Simulation shows that this learning algorithm can accurately recover known parameters of STEMMED, especially for small networks and long data-horizons. Next, we turn this node-by-node decomposition into an online cooperative multi-period forecasting framework, which is asymptotically robust to operational errors, to facilitate Opioid-related overdose death (OOD) trends forecasting among neighboring communities. In our numerical study, we parameterize STEMMED using individual-level OOD data and county-level demographics in Massachusetts. For any node, we observe that OODs within the same drug class from nearby locations have the greatest influence on future OOD trends. Furthermore, the expected proportion of OODs triggered by historical events varies greatly across counties, ranging between 30%-70%. Finally, in a practical online forecasting setting, STEMMED-based cooperative framework reduces prediction error by 60% on average, compared to well-established forecasting models. Leveraging the growing abundance of public health surveillance data, STEMMED can provide accurate forecasts of local OOD trends and highlight complex interactions between OODs across communities and drug types. Moreover, STEMMED enhances synergies between local and federal government entities, which is critical to designing impactful policy interventions. △ Less

Submitted 14 November, 2022; originally announced November 2022.

Supervised Class-pairwise NMF for Data Representation and Classification

Authors: Rachid Hedjam, Abdelhamid Abdesselam, Seyed Mohammad Jafar Jalali, Imran Khan, Samir Brahim Belhaouari

Abstract: Various Non-negative Matrix factorization (NMF) based methods add new terms to the cost function to adapt the model to specific tasks, such as clustering, or to preserve some structural properties in the reduced space (e.g., local invariance). The added term is mainly weighted by a hyper-parameter to control the balance of the overall formula to guide the optimization process towards the objective… ▽ More Various Non-negative Matrix factorization (NMF) based methods add new terms to the cost function to adapt the model to specific tasks, such as clustering, or to preserve some structural properties in the reduced space (e.g., local invariance). The added term is mainly weighted by a hyper-parameter to control the balance of the overall formula to guide the optimization process towards the objective. The result is a parameterized NMF method. However, NMF method adopts unsupervised approaches to estimate the factorizing matrices. Thus, the ability to perform prediction (e.g. classification) using the new obtained features is not guaranteed. The objective of this work is to design an evolutionary framework to learn the hyper-parameter of the parameterized NMF and estimate the factorizing matrices in a supervised way to be more suitable for classification problems. Moreover, we claim that applying NMF-based algorithms separately to different class-pairs instead of applying it once to the whole dataset improves the effectiveness of the matrix factorization process. This results in training multiple parameterized NMF algorithms with different balancing parameter values. A cross-validation combination learning framework is adopted and a Genetic Algorithm is used to identify the optimal set of hyper-parameter values. The experiments we conducted on both real and synthetic datasets demonstrated the effectiveness of the proposed approach. △ Less

Submitted 28 September, 2022; originally announced September 2022.

On convergence and optimality of maximum-likelihood APA

Authors: Shirin Jalali, Carl Nuzman, Yue Sun

Abstract: Affine projection algorithm (APA) is a well-known algorithm in adaptive filtering applications such as audio echo cancellation. APA relies on three parameters: $P$ (projection order), $μ$ (step size) and $δ$ (regularization parameter). It is known that running APA for a fixed set of parameters leads to a tradeoff between convergence speed and accuracy. Therefore, various methods for adaptively set… ▽ More Affine projection algorithm (APA) is a well-known algorithm in adaptive filtering applications such as audio echo cancellation. APA relies on three parameters: $P$ (projection order), $μ$ (step size) and $δ$ (regularization parameter). It is known that running APA for a fixed set of parameters leads to a tradeoff between convergence speed and accuracy. Therefore, various methods for adaptively setting the parameters have been proposed in the literature. Inspired by maximum likelihood (ML) estimation, we derive a new ML-based approach for adaptively setting the parameters of APA, which we refer to as ML-APA. For memoryless Gaussian inputs, we fully characterize the expected misalignment error of ML-APA as a function of iteration number and show that it converges to zero as $O({1\over t})$. We further prove that the achieved error is asymptotically optimal. ML-APA updates its estimate once every $P$ samples. We also propose incremental ML-APA (IML-APA), which updates the coefficients at every time step and outperforms ML-APA in our simulations results. Our simulation results verify the analytical conclusions for memoryless inputs and show that the new algorithms also perform well for strongly correlated input signals. △ Less

Submitted 12 October, 2023; v1 submitted 4 September, 2022; originally announced September 2022.

Is it always worthwhile to resolve the governing equations of plate theories for graded porosity along the thickness?

Authors: S. K. Jalali, M. J. Beigrezaee, Nicola M. Pugno

Abstract: Functionally graded porous (FGP) plates have been introduced as modern structural members which open a new window to optimal and functional designs. Despite the need to study the effect of graded porosity on the mechanical behavior of FGP plates, it is necessary to consider the very extensive and valuable literature in this field, presenting remarkable closed-form solutions. Hence, this paper aims… ▽ More Functionally graded porous (FGP) plates have been introduced as modern structural members which open a new window to optimal and functional designs. Despite the need to study the effect of graded porosity on the mechanical behavior of FGP plates, it is necessary to consider the very extensive and valuable literature in this field, presenting remarkable closed-form solutions. Hence, this paper aims to answer where is possible to implement the available exact solutions for the analysis of FGP plates. As the special distinction of FGP plates, graded porosity, is reflected in their stiffnesses and moments of inertia coefficients, 12 different functionality of porosity distribution along the thickness are considered and a set of explicit formulation for evaluating these coefficients are presented to be substituted in already provided analytical solutions. Many examples including bending and free vibration of thin and thick FGP plates are exhibited and the influence of the type of porosity distribution is discussed in details. This work can be considered as a guideline for designers to evaluate the effect of graded porosity based on the cornerstone of the huge number of solutions in the precious literature of plate theories. △ Less

Submitted 27 September, 2021; originally announced October 2021.

Journal ref: Composite Structures Volume 256, 15 January 2021, 112960

Optimal Order Simple Regret for Gaussian Process Bandits

Authors: Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, Da-shan Shiu

Abstract: Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function $f$. The problem can be cast as a Gaussian Process (GP) bandit where $f$ lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. W… ▽ More Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function $f$. The problem can be cast as a Gaussian Process (GP) bandit where $f$ lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When $N$ is the number of exploration trials and $γ_N$ is the maximal information gain, we prove an $\tilde{\mathcal{O}}(\sqrt{γ_N/N})$ bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest. △ Less

Submitted 20 August, 2021; originally announced August 2021.

Compressed sensing in the presence of speckle noise

Authors: Wenda Zhou, Shirin Jalali, Arian Maleki

Abstract: The problem of recovering a structured signal from its linear measurements in the presence of speckle noise is studied. This problem appears in many imaging systems such as synthetic aperture radar and optical coherence tomography. The current acquisition technology oversamples signals and converts the problem into a denoising problem with multiplicative noise. However, this paper explores the pos… ▽ More The problem of recovering a structured signal from its linear measurements in the presence of speckle noise is studied. This problem appears in many imaging systems such as synthetic aperture radar and optical coherence tomography. The current acquisition technology oversamples signals and converts the problem into a denoising problem with multiplicative noise. However, this paper explores the possibility of reducing the number of measurements below the ambient dimension of the signal. The sophistications that appear in the study of multiplicative noises have so far impeded theoretical analysis of such problems. This paper aims to present the first theoretical result regarding the recovery of signals from their undersampled measurements under the speckle noise. It is shown that if the signal class is structured, in the sense that the signals can be compressed efficiently, then one can obtain accurate estimates of the signal from fewer measurements than the ambient dimension. We demonstrate the effectiveness of the methods we propose through simulation results. △ Less

Submitted 31 July, 2021; originally announced August 2021.

Towards a Universal NLG for Dialogue Systems and Simulators with Future Bridging

Authors: Philipp Ennen, Yen-Ting Lin, Ali Girayhan Ozbay, Ferdinando Insalata, Maolin Li, Ye Tian, Sepehr Jalali, Da-shan Shiu

Abstract: In a dialogue system pipeline, a natural language generation (NLG) unit converts the dialogue direction and content to a corresponding natural language realization. A recent trend for dialogue systems is to first pre-train on large datasets and then fine-tune in a supervised manner using datasets annotated with application-specific features. Though novel behaviours can be learned from custom annot… ▽ More In a dialogue system pipeline, a natural language generation (NLG) unit converts the dialogue direction and content to a corresponding natural language realization. A recent trend for dialogue systems is to first pre-train on large datasets and then fine-tune in a supervised manner using datasets annotated with application-specific features. Though novel behaviours can be learned from custom annotation, the required effort severely bounds the quantity of the training set, and the application-specific nature limits the reuse. In light of the recent success of data-driven approaches, we propose the novel future bridging NLG (FBNLG) concept for dialogue systems and simulators. The critical step is for an FBNLG to accept a future user or system utterance to bridge the present context towards. Future bridging enables self supervised training over annotation-free datasets, decoupled the training of NLG from the rest of the system. An FBNLG, pre-trained with massive datasets, is expected to apply in classical or new dialogue scenarios with minimal adaptation effort. We evaluate a prototype FBNLG to show that future bridging can be a viable approach to a universal few-shot NLG for task-oriented and chit-chat dialogues. △ Less

Submitted 24 May, 2021; v1 submitted 21 May, 2021; originally announced May 2021.

Comments: 11 pages, 1 figure

On Measuring the Diversity of Organizational Networks

Authors: Zeinab S. Jalali, Krishnaram Kenthapadi, Sucheta Soundarajan

Abstract: The interaction patterns of employees in social and professional networks play an important role in the success of employees and organizations as a whole. However, in many fields there is a severe under-representation of minority groups; moreover, minority individuals may be segregated from the rest of the network or isolated from one another. While the problem of increasing the representation of… ▽ More The interaction patterns of employees in social and professional networks play an important role in the success of employees and organizations as a whole. However, in many fields there is a severe under-representation of minority groups; moreover, minority individuals may be segregated from the rest of the network or isolated from one another. While the problem of increasing the representation of minority groups in various fields has been well-studied, diver- sification in terms of numbers alone may not be sufficient: social relationships should also be considered. In this work, we consider the problem of assigning a set of employment candidates to positions in a social network so that diversity and overall fitness are maximized, and propose Fair Employee Assignment (FairEA), a novel algorithm for finding such a matching. The output from FairEA can be used as a benchmark by organizations wishing to evaluate their hiring and assignment practices. On real and synthetic networks, we demonstrate that FairEA does well at finding high-fitness, high-diversity matchings. △ Less

Submitted 14 May, 2021; originally announced May 2021.

Comments: 12 pages, 3 figures, accepted in CompleNet 2021

Relationship-based Neural Baby Talk

Authors: Fan Fu, Tingting Xie, Ioannis Patras, Sepehr Jalali

Abstract: Understanding interactions between objects in an image is an important element for generating captions. In this paper, we propose a relationship-based neural baby talk (R-NBT) model to comprehensively investigate several types of pairwise object interactions by encoding each image via three different relationship-based graph attention networks (GATs). We study three main relationships: \textit{spa… ▽ More Understanding interactions between objects in an image is an important element for generating captions. In this paper, we propose a relationship-based neural baby talk (R-NBT) model to comprehensively investigate several types of pairwise object interactions by encoding each image via three different relationship-based graph attention networks (GATs). We study three main relationships: \textit{spatial relationships} to explore geometric interactions, \textit{semantic relationships} to extract semantic interactions, and \textit{implicit relationships} to capture hidden information that could not be modelled explicitly as above. We construct three relationship graphs with the objects in an image as nodes, and the mutual relationships of pairwise objects as edges. By exploring features of neighbouring regions individually via GATs, we integrate different types of relationships into visual features of each node. Experiments on COCO dataset show that our proposed R-NBT model outperforms state-of-the-art models trained on COCO dataset in three image caption generation tasks. △ Less

Submitted 8 March, 2021; originally announced March 2021.

GAP-net for Snapshot Compressive Imaging

Authors: Ziyi Meng, Shirin Jalali, Xin Yuan

Abstract: Snapshot compressive imaging (SCI) systems aim to capture high-dimensional ($\ge3$D) images in a single shot using 2D detectors. SCI devices include two main parts: a hardware encoder and a software decoder. The hardware encoder typically consists of an (optical) imaging system designed to capture {compressed measurements}. The software decoder on the other hand refers to a reconstruction algorith… ▽ More Snapshot compressive imaging (SCI) systems aim to capture high-dimensional ($\ge3$D) images in a single shot using 2D detectors. SCI devices include two main parts: a hardware encoder and a software decoder. The hardware encoder typically consists of an (optical) imaging system designed to capture {compressed measurements}. The software decoder on the other hand refers to a reconstruction algorithm that retrieves the desired high-dimensional signal from those measurements. In this paper, using deep unfolding ideas, we propose an SCI recovery algorithm, namely GAP-net, which unfolds the generalized alternating projection (GAP) algorithm. At each stage, GAP-net passes its current estimate of the desired signal through a trained convolutional neural network (CNN). The CNN operates as a denoiser that projects the estimate back to the desired signal space. For the GAP-net that employs trained auto-encoder-based denoisers, we prove a probabilistic global convergence result. Finally, we investigate the performance of GAP-net in solving video SCI and spectral SCI problems. In both cases, GAP-net demonstrates competitive performance on both synthetic and real data. In addition to having high accuracy and high speed, we show that GAP-net is flexible with respect to signal modulation implying that a trained GAP-net decoder can be applied in different systems. Our code is at https://github.com/mengziyi64/ADMM-net. △ Less

Submitted 13 December, 2020; originally announced December 2020.

Comments: 30 pages, 14 figures; State-of-the-art algorithms for Snapshot Compressive Imaging

Cyclic orthogonal convolutions for long-range integration of features

Authors: Federica Freddi, Jezabel R Garcia, Michael Bromberg, Sepehr Jalali, Da-Shan Shiu, Alvin Chua, Alberto Bernacchia

Abstract: In Convolutional Neural Networks (CNNs) information flows across a small neighbourhood of each pixel of an image, preventing long-range integration of features before reaching deep layers in the network. We propose a novel architecture that allows flexible information flow between features $z$ and locations $(x,y)$ across the entire image with a small number of layers. This architecture uses a cyc… ▽ More In Convolutional Neural Networks (CNNs) information flows across a small neighbourhood of each pixel of an image, preventing long-range integration of features before reaching deep layers in the network. We propose a novel architecture that allows flexible information flow between features $z$ and locations $(x,y)$ across the entire image with a small number of layers. This architecture uses a cycle of three orthogonal convolutions, not only in $(x,y)$ coordinates, but also in $(x,z)$ and $(y,z)$ coordinates. We stack a sequence of such cycles to obtain our deep network, named CycleNet. As this only requires a permutation of the axes of a standard convolution, its performance can be directly compared to a CNN. Our model obtains competitive results at image classification on CIFAR-10 and ImageNet datasets, when compared to CNNs of similar size. We hypothesise that long-range integration favours recognition of objects by shape rather than texture, and we show that CycleNet transfers better than CNNs to stylised images. On the Pathfinder challenge, where integration of distant features is crucial, CycleNet outperforms CNNs by a large margin. We also show that even when employing a small convolutional kernel, the size of receptive fields of CycleNet reaches its maximum after one cycle, while conventional CNNs require a large number of layers. △ Less

Submitted 11 December, 2020; originally announced December 2020.

Comments: 11 pages, 5 figures

SpinalNet: Deep Neural Network with Gradual Input

Authors: H M Dipu Kabir, Moloud Abdar, Seyed Mohammad Jafar Jalali, Abbas Khosravi, Amir F Atiya, Saeid Nahavandi, Dipti Srinivasan

Abstract: Deep neural networks (DNNs) have achieved the state of the art performance in numerous fields. However, DNNs need high computation times, and people always expect better performance in a lower computation. Therefore, we study the human somatosensory system and design a neural network (SpinalNet) to achieve higher accuracy with fewer computations. Hidden layers in traditional NNs receive inputs in… ▽ More Deep neural networks (DNNs) have achieved the state of the art performance in numerous fields. However, DNNs need high computation times, and people always expect better performance in a lower computation. Therefore, we study the human somatosensory system and design a neural network (SpinalNet) to achieve higher accuracy with fewer computations. Hidden layers in traditional NNs receive inputs in the previous layer, apply activation function, and then transfer the outcomes to the next layer. In the proposed SpinalNet, each layer is split into three splits: 1) input split, 2) intermediate split, and 3) output split. Input split of each layer receives a part of the inputs. The intermediate split of each layer receives outputs of the intermediate split of the previous layer and outputs of the input split of the current layer. The number of incoming weights becomes significantly lower than traditional DNNs. The SpinalNet can also be used as the fully connected or classification layer of DNN and supports both traditional learning and transfer learning. We observe significant error reductions with lower computational costs in most of the DNNs. Traditional learning on the VGG-5 network with SpinalNet classification layers provided the state-of-the-art (SOTA) performance on QMNIST, Kuzushiji-MNIST, EMNIST (Letters, Digits, and Balanced) datasets. Traditional learning with ImageNet pre-trained initial weights and SpinalNet classification layers provided the SOTA performance on STL-10, Fruits 360, Bird225, and Caltech-101 datasets. The scripts of the proposed SpinalNet are available at the following link: https://github.com/dipuk0506/SpinalNet △ Less

Submitted 7 January, 2022; v1 submitted 7 July, 2020; originally announced July 2020.

An Ultra-Efficient Memristor-Based DNN Framework with Structured Weight Pruning and Quantization Using ADMM

Authors: Geng Yuan, Xiaolong Ma, Caiwen Ding, Sheng Lin, Tianyun Zhang, Zeinab S. Jalali, Yilong Zhao, Li Jiang, Sucheta Soundarajan, Yanzhi Wang

Abstract: The high computation and memory storage of large deep neural networks (DNNs) models pose intensive challenges to the conventional Von-Neumann architecture, incurring substantial data movements in the memory hierarchy. The memristor crossbar array has emerged as a promising solution to mitigate the challenges and enable low-power acceleration of DNNs. Memristor-based weight pruning and weight quant… ▽ More The high computation and memory storage of large deep neural networks (DNNs) models pose intensive challenges to the conventional Von-Neumann architecture, incurring substantial data movements in the memory hierarchy. The memristor crossbar array has emerged as a promising solution to mitigate the challenges and enable low-power acceleration of DNNs. Memristor-based weight pruning and weight quantization have been seperately investigated and proven effectiveness in reducing area and power consumption compared to the original DNN model. However, there has been no systematic investigation of memristor-based neuromorphic computing (NC) systems considering both weight pruning and weight quantization. In this paper, we propose an unified and systematic memristor-based framework considering both structured weight pruning and weight quantization by incorporating alternating direction method of multipliers (ADMM) into DNNs training. We consider hardware constraints such as crossbar blocks pruning, conductance range, and mismatch between weight value and real devices, to achieve high accuracy and low power and small area footprint. Our framework is mainly integrated by three steps, i.e., memristor-based ADMM regularized optimization, masked mapping and retraining. Experimental results show that our proposed framework achieves 29.81X (20.88X) weight compression ratio, with 98.38% (96.96%) and 98.29% (97.47%) power and area reduction on VGG-16 (ResNet-18) network where only have 0.5% (0.76%) accuracy loss, compared to the original DNN models. We share our models at link http://bit.ly/2Jp5LHJ. △ Less

Submitted 28 August, 2019; originally announced August 2019.

Incorporating fault-proneness estimations into coverage-based test case prioritization methods

Authors: Mostafa Mahdieh, Seyed-Hassan Mirian-Hosseinabadi, Khashayar Etemadi, Ali Nosrati, Sajad Jalali

Abstract: Context: During the development process of a software program, regression testing is used to ensure that the correct behavior of the software is retained after updates to the source code. This regression testing becomes costly over time as the number of test cases increases and it makes sense to prioritize test cases in order to execute fault-detecting test cases as soon as possible. There are man… ▽ More Context: During the development process of a software program, regression testing is used to ensure that the correct behavior of the software is retained after updates to the source code. This regression testing becomes costly over time as the number of test cases increases and it makes sense to prioritize test cases in order to execute fault-detecting test cases as soon as possible. There are many coverage-based test case prioritization (TCP) methods that only use the code coverage data to prioritize test cases. By incorporating the fault-proneness estimations of code units into the coverage-based TCP methods, we can improve such techniques. Objective: In this paper, we aim to propose an approach which improves coverage-based TCP methods by considering the fault-proneness distribution over code units. Further, we present the results of an empirical study that shows using our proposed approach significantly improves the additional strategy, which is a widely used coverage-based TCP method. Method: The approach presented in this study uses the bug history of the software in order to introduce a defect prediction method to learn a neural network model. This model is then used to estimate fault-proneness of each area of the source code and then the estimations are incorporated into coverage-based TCP methods. Our proposed approach is a general idea that can be applied to many coverage-based methods, such as the additional and total TCP methods. Results: The proposed methods are evaluated on datasets collected from the development history of five real-world projects including 357 versions in total. The experiments show that using an appropriate bug history can improve coverage-based TCP methods. △ Less

Submitted 16 February, 2020; v1 submitted 18 August, 2019; originally announced August 2019.

Efficient Deep Learning of GMMs

Authors: Shirin Jalali, Carl Nuzman, Iraj Saniee

Abstract: We show that a collection of Gaussian mixture models (GMMs) in $R^{n}$ can be optimally classified using $O(n)$ neurons in a neural network with two hidden layers (deep neural network), whereas in contrast, a neural network with a single hidden layer (shallow neural network) would require at least $O(\exp(n))$ neurons or possibly exponentially large coefficients. Given the universality of the Gaus… ▽ More We show that a collection of Gaussian mixture models (GMMs) in $R^{n}$ can be optimally classified using $O(n)$ neurons in a neural network with two hidden layers (deep neural network), whereas in contrast, a neural network with a single hidden layer (shallow neural network) would require at least $O(\exp(n))$ neurons or possibly exponentially large coefficients. Given the universality of the Gaussian distribution in the feature spaces of data, e.g., in speech, image and text, our result sheds light on the observed efficiency of deep neural networks in practical classification problems. △ Less

Submitted 15 February, 2019; originally announced February 2019.

Denoising of structured random processes

Authors: Wenda Zhou, Shirin Jalali

Abstract: Denoising stationary process $(X_i)_{i \in Z}$ corrupted by additive white Gaussian noise is a classic and fundamental problem in information theory and statistical signal processing. Despite considerable progress in designing efficient denoising algorithms, for general analog sources, theoretically-founded computationally-efficient methods are yet to be found. For instance in denoising $X^n$ corr… ▽ More Denoising stationary process $(X_i)_{i \in Z}$ corrupted by additive white Gaussian noise is a classic and fundamental problem in information theory and statistical signal processing. Despite considerable progress in designing efficient denoising algorithms, for general analog sources, theoretically-founded computationally-efficient methods are yet to be found. For instance in denoising $X^n$ corrupted by noise $Z^n$ as $Y^n=X^n+Z^n$, given the full distribution of $X^n$, a minimum mean square error (MMSE) denoiser needs to compute $E[X^n|Y^n]$. However, for general sources, computing $E[X^n|Y^n]$ is computationally very challenging, if not infeasible. In this paper, starting by a Bayesian setup, where the source distribution is fully known, a novel denoising method, namely, quantized maximum a posteriori (Q-MAP) denoiser, is proposed and its asymptotic performance in the high signal to noise ratio regime is analyzed. Both for memoryless sources, and for structured first-order Markov sources, it is shown that, asymptotically, as $σ$ converges to zero, ${1\over σ^2}E[(X_i-\hat{X}^{\rm Q-MAP}_i)^2]$ achieved by Q-MAP denoiser converges to the information dimension of the source. For the studied memoryless sources, this limit is known to be optimal. A key advantage of the Q-MAP denoiser is that, unlike an MMSE denoiser, it highlights the key properties of the source distribution that are to be used in its denoising. This property dramatically reduces the computational complexity of approximating the solution of the Q-MAP denoiser. Additionally, it naturally leads to a learning-based denoiser. Using ImageNet database for training, initial simulation results exploring the performance of such a learning-based denoiser in image denoising are presented. △ Less

Submitted 21 January, 2019; v1 submitted 17 January, 2019; originally announced January 2019.

Solving inverse problems via auto-encoders

Authors: Pei Peng, Shirin Jalali, Xin Yuan

Abstract: Compressed sensing (CS) is about recovering a structured signal from its under-determined linear measurements. Starting from sparsity, recovery methods have steadily moved towards more complex structures. Emerging machine learning tools such as generative functions that are based on neural networks are able to learn general complex structures from training data. This makes them potentially powerfu… ▽ More Compressed sensing (CS) is about recovering a structured signal from its under-determined linear measurements. Starting from sparsity, recovery methods have steadily moved towards more complex structures. Emerging machine learning tools such as generative functions that are based on neural networks are able to learn general complex structures from training data. This makes them potentially powerful tools for designing CS algorithms. Consider a desired class of signals $\cal Q$, ${\cal Q}\subset{R}^n$, and a corresponding generative function $g:{\cal U}^k\rightarrow {R}^n$, ${\cal U}\subset {R}$, such that $\sup_{{\bf x}\in {\cal Q}}\min_{{\bf u}\in{\cal U}^k}{1\over \sqrt{n}}\|g({\bf u})-{\bf x}\|\leq δ$. A recovery method based on $g$ seeks $g({\bf u})$ with minimum measurement error. In this paper, the performance of such a recovery method is studied, under both noisy and noiseless measurements. In the noiseless case, roughly speaking, it is proven that, as $k$ and $n$ grow without bound and $δ$ converges to zero, if the number of measurements ($m$) is larger than the input dimension of the generative model ($k$), then asymptotically, almost lossless recovery is possible. Furthermore, the performance of an efficient iterative algorithm based on projected gradient descent is studied. In this case, an auto-encoder is used to define and enforce the source structure at the projection step. The auto-encoder is defined by encoder and decoder (generative) functions $f:{R}^n\to{\cal U}^k$ and $g:{\cal U}^k\to{R}^n$, respectively. We theoretically prove that, roughly, given $m>40k\log{1\over δ}$ measurements, such an algorithm converges to the vicinity of the desired result, even in the presence of additive white Gaussian noise. Numerical results exploring the effectiveness of the proposed method are presented. △ Less

Submitted 17 December, 2019; v1 submitted 15 January, 2019; originally announced January 2019.

M2U-Net: Effective and Efficient Retinal Vessel Segmentation for Resource-Constrained Environments

Authors: Tim Laibacher, Tillman Weyde, Sepehr Jalali

Abstract: In this paper, we present a novel neural network architecture for retinal vessel segmentation that improves over the state of the art on two benchmark datasets, is the first to run in real time on high resolution images, and its small memory and processing requirements make it deployable in mobile and embedded systems. The M2U-Net has a new encoder-decoder architecture that is inspired by the U-Ne… ▽ More In this paper, we present a novel neural network architecture for retinal vessel segmentation that improves over the state of the art on two benchmark datasets, is the first to run in real time on high resolution images, and its small memory and processing requirements make it deployable in mobile and embedded systems. The M2U-Net has a new encoder-decoder architecture that is inspired by the U-Net. It adds pretrained components of MobileNetV2 in the encoder part and novel contractive bottleneck blocks in the decoder part that, combined with bilinear upsampling, drastically reduce the parameter count to 0.55M compared to 31.03M in the original U-Net. We have evaluated its performance against a wide body of previously published results on three public datasets. On two of them, the M2U-Net achieves new state-of-the-art performance by a considerable margin. When implemented on a GPU, our method is the first to achieve real-time inference speeds on high-resolution fundus images. We also implemented our proposed network on an ARM-based embedded system where it segments images in between 0.6 and 15 sec, depending on the resolution. Thus, the M2U-Net enables a number of applications of retinal vessel structure extraction, such as early diagnosis of eye diseases, retinal biometric authentication systems, and robot assisted microsurgery. △ Less

Submitted 23 April, 2019; v1 submitted 19 November, 2018; originally announced November 2018.

Snapshot compressed sensing: performance bounds and algorithms

Authors: Shirin Jalali, Xin Yuan

Abstract: Snapshot compressed sensing (CS) refers to compressive imaging systems in which multiple frames are mapped into a single measurement frame. Each pixel in the acquired frame is a noisy linear mapping of the corresponding pixels in the frames that are combined together. While the problem can be cast as a CS problem, due to the very special structure of the sensing matrix, standard CS theory cannot b… ▽ More Snapshot compressed sensing (CS) refers to compressive imaging systems in which multiple frames are mapped into a single measurement frame. Each pixel in the acquired frame is a noisy linear mapping of the corresponding pixels in the frames that are combined together. While the problem can be cast as a CS problem, due to the very special structure of the sensing matrix, standard CS theory cannot be employed to study such systems. In this paper, a compression-based framework is employed for theoretical analysis of snapshot CS systems. It is shown that this framework leads to two novel, computationally-efficient and theoretically-analyzable compression-based recovery algorithms. The proposed methods are iterative and employ compression codes to define and impose the structure of the desired signal. Theoretical convergence guarantees are derived for both algorithms. In the simulations, it is shown that, in the cases of both noise-free and noisy measurements, combining the proposed algorithms with a customized video compression code, designed to exploit nonlocal structures of video frames, significantly improves the state-of-the-art performance. △ Less

Submitted 29 April, 2019; v1 submitted 10 August, 2018; originally announced August 2018.

Comments: 43 pages

Theoretical links between universal and Bayesian compressed sensing algorithms

Authors: Shirin Jalali

Abstract: Quantized maximum a posteriori (Q-MAP) is a recently-proposed Bayesian compressed sensing algorithm that, given the source distribution, recovers $X^n$ from its linear measurements $Y^m=AX^n$, where $A\in R^{m\times n}$ denotes the known measurement matrix. On the other hand, Lagrangian minimum entropy pursuit (L-MEP) is a universal compressed sensing algorithm that aims at recovering $X^n$ from i… ▽ More Quantized maximum a posteriori (Q-MAP) is a recently-proposed Bayesian compressed sensing algorithm that, given the source distribution, recovers $X^n$ from its linear measurements $Y^m=AX^n$, where $A\in R^{m\times n}$ denotes the known measurement matrix. On the other hand, Lagrangian minimum entropy pursuit (L-MEP) is a universal compressed sensing algorithm that aims at recovering $X^n$ from its linear measurements $Y^m=AX^n$, without having access to the source distribution. Both Q-MAP and L-MEP provably achieve the minimum required sampling rates, in noiseless cases where such fundamental limits are known. L-MEP is based on minimizing a cost function that consists of a linear combination of the conditional empirical entropy of a potential reconstruction vector and its corresponding measurement error. In this paper, using a first-order linear approximation of the conditional empirical entropy function, L-MEP is connected with Q-MAP. The established connection between L-MEP and Q-MAP leads to variants of Q-MAP which have the same asymptotic performance as Q-MAP in terms of their required sampling rates. Moreover, these variants suggest that Q-MAP is robust to small error in estimating the source distribution. This robustness is theoretically proven and the effect of a non-vanishing estimation error on the required sampling rate is characterized. △ Less

Submitted 3 January, 2018; originally announced January 2018.

Linear Time Clustering for High Dimensional Mixtures of Gaussian Clouds

Authors: Dan Kushnir, Shirin Jalali, Iraj Saniee

Abstract: Clustering mixtures of Gaussian distributions is a fundamental and challenging problem that is ubiquitous in various high-dimensional data processing tasks. While state-of-the-art work on learning Gaussian mixture models has focused primarily on improving separation bounds and their generalization to arbitrary classes of mixture models, less emphasis has been paid to practical computational effici… ▽ More Clustering mixtures of Gaussian distributions is a fundamental and challenging problem that is ubiquitous in various high-dimensional data processing tasks. While state-of-the-art work on learning Gaussian mixture models has focused primarily on improving separation bounds and their generalization to arbitrary classes of mixture models, less emphasis has been paid to practical computational efficiency of the proposed solutions. In this paper, we propose a novel and highly efficient clustering algorithm for $n$ points drawn from a mixture of two arbitrary Gaussian distributions in $\mathbb{R}^p$. The algorithm involves performing random 1-dimensional projections until a direction is found that yields a user-specified clustering error $e$. For a 1-dimensional separation parameter $γ$ satisfying $γ=Q^{-1}(e)$, the expected number of such projections is shown to be bounded by $o(\ln p)$, when $γ$ satisfies $γ\leq c\sqrt{\ln{\ln{p}}}$, with $c$ as the separability parameter of the two Gaussians in $\mathbb{R}^p$. Consequently, the expected overall running time of the algorithm is linear in $n$ and quasi-linear in $p$ at $o(\ln{p})O(np)$, and the sample complexity is independent of $p$. This result stands in contrast to prior works which provide polynomial, with at-best quadratic, running time in $p$ and $n$. We show that our bound on the expected number of 1-dimensional projections extends to the case of three or more Gaussian components, and we present a generalization of our results to mixture distributions beyond the Gaussian model. △ Less

Submitted 1 March, 2018; v1 submitted 19 December, 2017; originally announced December 2017.

Using Black-box Compression Algorithms for Phase Retrieval

Authors: Milad Bakhshizadeh, Arian Maleki, Shirin Jalali

Abstract: Compressive phase retrieval refers to the problem of recovering a structured $n$-dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of measurements makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, algorithms designed in this area are developed to take advantage of si… ▽ More Compressive phase retrieval refers to the problem of recovering a structured $n$-dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of measurements makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, algorithms designed in this area are developed to take advantage of simple structures such as sparsity and its convex generalizations. The goal of this paper is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to $κ$, the $α$-dimension (closely related to the rate-distortion dimension) of the given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization, if the number of measurements is larger than $ C κ^2 \log^2 n$, where $C$ is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the superb performance of the resulting algorithm on real-world images. △ Less

Submitted 8 June, 2020; v1 submitted 8 December, 2017; originally announced December 2017.

Comments: 43 pages

Decision-Making and Biases in Cybersecurity Capability Development: Evidence from a Simulation Game Experiment

Authors: M. S. Jalali

Abstract: We developed a simulation game to study the effectiveness of decision-makers in overcoming two complexities in building cybersecurity capabilities: potential delays in capability development; and uncertainties in predicting cyber incidents. Analyzing 1,479 simulation runs, we compared the performances of a group of experienced professionals with those of an inexperienced control group. Experienced… ▽ More We developed a simulation game to study the effectiveness of decision-makers in overcoming two complexities in building cybersecurity capabilities: potential delays in capability development; and uncertainties in predicting cyber incidents. Analyzing 1,479 simulation runs, we compared the performances of a group of experienced professionals with those of an inexperienced control group. Experienced subjects did not understand the mechanisms of delays any better than inexperienced subjects; however, experienced subjects were better able to learn the need for proactive decision-making through an iterative process. Both groups exhibited similar errors when dealing with the uncertainty of cyber incidents. Our findings highlight the importance of training for decision-makers with a focus on systems thinking skills, and lay the groundwork for future research on uncovering mental biases about the complexities of cybersecurity. △ Less

Submitted 2 July, 2018; v1 submitted 4 July, 2017; originally announced July 2017.

An efficient algorithm for compression-based compressed sensing

Authors: Sajjad Beygi, Shirin Jalali, Arian Maleki, Urbashi Mitra

Abstract: Modern image and video compression codes employ elaborate structures existing in such signals to encode them into few number of bits. Compressed sensing recovery algorithms on the other hand use such signals' structures to recover them from few linear observations. Despite the steady progress in the field of compressed sensing, structures that are often used for signal recovery are still much simp… ▽ More Modern image and video compression codes employ elaborate structures existing in such signals to encode them into few number of bits. Compressed sensing recovery algorithms on the other hand use such signals' structures to recover them from few linear observations. Despite the steady progress in the field of compressed sensing, structures that are often used for signal recovery are still much simpler than those employed by state-of-the-art compression codes. The main goal of this paper is to bridge this gap through answering the following question: Can one employ a given compression code to build an efficient (polynomial time) compressed sensing recovery algorithm? In response to this question, the compression-based gradient descent (C-GD) algorithm is proposed. C-GD, which is a low-complexity iterative algorithm, is able to employ a generic compression code for compressed sensing and therefore elevates the scope of structures used in compressed sensing to those used by compression codes. The convergence performance of C-GD and its required number of measurements in terms of the rate-distortion performance of the compression code are theoretically analyzed. It is also shown that C-GD is robust to additive white Gaussian noise. Finally, the presented simulation results show that combining C-GD with commercial image compression codes such as JPEG2000 yields state-of-the-art performance in imaging applications. △ Less

Submitted 6 April, 2017; originally announced April 2017.

On the Impact of a Single Edge on the Network Coding Capacity

Authors: Shirin Jalali, Michelle Effros, Tracey Ho

Abstract: In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $δ$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $δ$ cannot change the capacity region… ▽ More In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $δ$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $δ$ cannot change the capacity region of the network by more than $δ$ in each dimension. In this paper, we extend this result to the case of multi-source, multi-sink networks for some special network topologies. △ Less

Submitted 22 July, 2016; originally announced July 2016.

Comments: Originally presented at ITA 2011 in San Diego, CA. The arXiv version contains an updated proof of Theorem 1

Rate-Distortion Dimension of Stochastic Processes

Authors: Farideh Ebrahim Rezagah, Shirin Jalali, Elza Erkip, H. Vincent Poor

Abstract: The rate-distortion dimension (RDD) of an analog stationary process is studied as a measure of complexity that captures the amount of information contained in the process. It is shown that the RDD of a process, defined as two times the asymptotic ratio of its rate-distortion function $R(D)$ to $\log {1\over D}$ as the distortion $D$ approaches zero, is equal to its information dimension (ID). This… ▽ More The rate-distortion dimension (RDD) of an analog stationary process is studied as a measure of complexity that captures the amount of information contained in the process. It is shown that the RDD of a process, defined as two times the asymptotic ratio of its rate-distortion function $R(D)$ to $\log {1\over D}$ as the distortion $D$ approaches zero, is equal to its information dimension (ID). This generalizes an earlier result by Kawabata and Dembo and provides an operational approach to evaluate the ID of a process, which previously was shown to be closely related to the effective dimension of the underlying process and also to the fundamental limits of compressed sensing. The relation between RDD and ID is illustrated for a piecewise constant process. △ Less

Submitted 22 July, 2016; originally announced July 2016.

Comments: Presented at 2016 IEEE International Symposium on Information Theory

New approach to Bayesian high-dimensional linear regression

Authors: Shirin Jalali, Arian Maleki

Abstract: Consider the problem of estimating parameters $X^n \in \mathbb{R}^n $, generated by a stationary process, from $m$ response variables $Y^m = AX^n+Z^m$, under the assumption that the distribution of $X^n$ is known. This is the most general version of the Bayesian linear regression problem. The lack of computationally feasible algorithms that can employ generic prior distributions and provide a good… ▽ More Consider the problem of estimating parameters $X^n \in \mathbb{R}^n $, generated by a stationary process, from $m$ response variables $Y^m = AX^n+Z^m$, under the assumption that the distribution of $X^n$ is known. This is the most general version of the Bayesian linear regression problem. The lack of computationally feasible algorithms that can employ generic prior distributions and provide a good estimate of $X^n$ has limited the set of distributions researchers use to model the data. In this paper, a new scheme called Q-MAP is proposed. The new method has the following properties: (i) It has similarities to the popular MAP estimation under the noiseless setting. (ii) In the noiseless setting, it achieves the "asymptotically optimal performance" when $X^n$ has independent and identically distributed components. (iii) It scales favorably with the dimensions of the problem and therefore is applicable to high-dimensional setups. (iv) The solution of the Q-MAP optimization can be found via a proposed iterative algorithm which is provably robust to the error (noise) in the response variables. △ Less

Submitted 6 April, 2017; v1 submitted 9 July, 2016; originally announced July 2016.

Compression-Based Compressed Sensing

Authors: Farideh Ebrahim Rezagah, Shirin Jalali, Elza Erkip, H. Vincent Poor

Abstract: Modern compression algorithms exploit complex structures that are present in signals to describe them very efficiently. On the other hand, the field of compressed sensing is built upon the observation that "structured" signals can be recovered from their under-determined set of linear projections. Currently, there is a large gap between the complexity of the structures studied in the area of compr… ▽ More Modern compression algorithms exploit complex structures that are present in signals to describe them very efficiently. On the other hand, the field of compressed sensing is built upon the observation that "structured" signals can be recovered from their under-determined set of linear projections. Currently, there is a large gap between the complexity of the structures studied in the area of compressed sensing and those employed by the state-of-the-art compression codes. Recent results in the literature on deterministic signals aim at bridging this gap through devising compressed sensing decoders that employ compression codes. This paper focuses on structured stochastic processes and studies the application of rate-distortion codes to compressed sensing of such signals. The performance of the formerly-proposed compressible signal pursuit (CSP) algorithm is studied in this stochastic setting. It is proved that in the very low distortion regime, as the blocklength grows to infinity, the CSP algorithm reliably and robustly recovers $n$ instances of a stationary process from random linear projections as long as their count is slightly more than $n$ times the rate-distortion dimension (RDD) of the source. It is also shown that under some regularity conditions, the RDD of a stationary process is equal to its information dimension (ID). This connection establishes the optimality of the CSP algorithm at least for memoryless stationary sources, for which the fundamental limits are known. Finally, it is shown that the CSP algorithm combined by a family of universal variable-length fixed-distortion compression codes yields a family of universal compressed sensing recovery algorithms. △ Less

Submitted 7 January, 2016; originally announced January 2016.

Outage Performance of Uplink Two-tier Networks Under Backhaul Constraints

Authors: Shirin Jalali, Zolfa Zeinalpour-Yazdi, H. Vincent Poor

Abstract: Multi-tier cellular communication networks constitute a promising approach to expand the coverage of cellular networks and enable them to offer higher data rates. In this paper, an uplink two-tier communication network is studied, in which macro users, femto users and femto access points are geometrically located inside the coverage area of a macro base station according to Poisson point processes… ▽ More Multi-tier cellular communication networks constitute a promising approach to expand the coverage of cellular networks and enable them to offer higher data rates. In this paper, an uplink two-tier communication network is studied, in which macro users, femto users and femto access points are geometrically located inside the coverage area of a macro base station according to Poisson point processes. Each femtocell is assumed to have a fixed backhaul constraint that puts a limit on the maximum number of femto and macro users it can service. Under this backhaul constraint, the network adopts a special open access policy, in which each macro user is either assigned to its closest femto access point or to the macro base station, depending on the ratio between its distances from those two. Under this model, upper and lower bounds on the outage probabilities experienced by users serviced by femto access points are derived as functions of the distance between the macro base station and the femto access point serving them. Similarly, upper and lower bounds on the outage probabilities of the users serviced by the macro base station are obtained. The bounds in both cases are confirmed via simulation results. △ Less

Submitted 30 November, 2014; originally announced December 2014.

Universal Compressed Sensing

Authors: Shirin Jalali, H. Vincent Poor

Abstract: In this paper, the problem of developing universal algorithms for compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then a minimum entropy pursuit (MEP) o… ▽ More In this paper, the problem of developing universal algorithms for compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then a minimum entropy pursuit (MEP) optimization approach is proposed, and it is proven that it can reliably recover any stationary process satisfying some mixing constraints from sufficient number of randomized linear measurements, without having any prior information about the distribution of the process. It is proved that a Lagrangian-type approximation of the MEP optimization problem, referred to as Lagrangian-MEP problem, is identical to a heuristic implementable algorithm proposed by Baron et al. It is shown that for the right choice of parameters the Lagrangian-MEP algorithm, in addition to having the same asymptotic performance as MEP optimization, is also robust to the measurement noise. For memoryless sources with a discrete-continuous mixture distribution, the fundamental limits of the minimum number of required measurements by a non-universal compressed sensing decoder is characterized by Wu et al. For such sources, it is proved that there is no loss in universal coding, and both the MEP and the Lagrangian-MEP asymptotically achieve the optimal performance. △ Less

Submitted 26 January, 2016; v1 submitted 30 June, 2014; originally announced June 2014.

Outage Analysis of Uplink Two-tier Networks

Authors: Zolfa Zeinalpour-Yazdi, Shirin Jalali

Abstract: Employing multi-tier networks is among the most promising approaches to address the rapid growth of the data demand in cellular networks. In this paper, we study a two-tier uplink cellular network consisting of femtocells and a macrocell. Femto base stations, and femto and macro users are assumed to be spatially deployed based on independent Poisson point processes. We consider an open access assi… ▽ More Employing multi-tier networks is among the most promising approaches to address the rapid growth of the data demand in cellular networks. In this paper, we study a two-tier uplink cellular network consisting of femtocells and a macrocell. Femto base stations, and femto and macro users are assumed to be spatially deployed based on independent Poisson point processes. We consider an open access assignment policy, where each macro user based on the ratio between its distances from its nearest femto access point (FAP) and from the macro base station (MBS) is assigned to either of them. By tuning the threshold, this policy allows controlling the coverage areas of FAPs. For a fixed threshold, femtocells coverage areas depend on their distances from the MBS; Those closest to the fringes will have the largest coverage areas. Under this open-access policy, ignoring the additive noise, we derive analytical upper and lower bounds on the outage probabilities of femto users and macro users that are subject to fading and path loss. We also study the effect of the distance from the MBS on the outage probability experienced by the users of a femtocell. In all cases, our simulation results comply with our analytical bounds. △ Less

Submitted 5 August, 2014; v1 submitted 12 December, 2013; originally announced December 2013.

From compression to compressed sensing

Authors: Shirin Jalali, Arian Maleki

Abstract: Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms $\mathcal{C}_r$, parametrized by rate $r$, for a compact class of signals $\mathcal{Q} \subset \mathds{R}^n$.… ▽ More Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms $\mathcal{C}_r$, parametrized by rate $r$, for a compact class of signals $\mathcal{Q} \subset \mathds{R}^n$. The set of natural images and JPEG at different rates are examples of $\mathcal{Q}$ and $\mathcal{C}_r$, respectively. We establish a connection between the rate-distortion performance of $\mathcal{C}_r$, and the number of linear measurements required for successful recovery in CS. We then propose compressible signal pursuit (CSP) algorithm and prove that, with high probability, it accurately and robustly recovers signals from an underdetermined set of linear measurements. We also explore the performance of CSP in the recovery of infinite dimensional signals. △ Less

Submitted 10 July, 2013; v1 submitted 17 December, 2012; originally announced December 2012.

On Capacity Region of Wiretap Networks

Authors: Shirin Jalali, Tracey Ho

Abstract: In this paper we consider the problem of secure network coding where an adversary has access to an unknown subset of links chosen from a known collection of links subsets. We study the capacity region of such networks, commonly called "wiretap networks", subject to weak and strong secrecy constraints, and consider both zero-error and asymptotically zero-error communication. We prove that in genera… ▽ More In this paper we consider the problem of secure network coding where an adversary has access to an unknown subset of links chosen from a known collection of links subsets. We study the capacity region of such networks, commonly called "wiretap networks", subject to weak and strong secrecy constraints, and consider both zero-error and asymptotically zero-error communication. We prove that in general discrete memoryless networks modeled by discrete memoryless channels, the capacity region subject to strong secrecy requirement and the capacity region subject to weak secrecy requirement are equal. In particular, this result shows that requiring strong secrecy in a wiretap network with asymptotically zero probability of error does not shrink the capacity region compared to the case of weak secrecy requirement. We also derive inner and outer bounds on the network coding capacity region of wiretap networks subject to weak secrecy constraint, for both zero probability of error and asymptotically zero probability of error, in terms of the entropic region. △ Less

Submitted 24 November, 2013; v1 submitted 16 December, 2012; originally announced December 2012.

Minimum Complexity Pursuit for Universal Compressed Sensing

Authors: Shirin Jalali, Arian Maleki, Richard Baraniuk

Abstract: The nascent field of compressed sensing is founded on the fact that high-dimensional signals with "simple structure" can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered, namely: What are the… ▽ More The nascent field of compressed sensing is founded on the fact that high-dimensional signals with "simple structure" can be recovered accurately from just a small number of randomized samples. Several specific kinds of structures have been explored in the literature, from sparsity and group sparsity to low-rankness. However, two fundamental questions have been left unanswered, namely: What are the general abstract meanings of "structure" and "simplicity"? And do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we address these two questions. Using algorithmic information theory tools such as the Kolmogorov complexity, we provide a unified definition of structure and simplicity. Leveraging this new definition, we develop and analyze an abstract algorithm for signal recovery motivated by Occam's Razor.Minimum complexity pursuit (MCP) requires just O(3κ) randomized samples to recover a signal of complexity κand ambient dimension n. We also discuss the performance of MCP in the presence of measurement noise and with approximately simple signals. △ Less

Submitted 5 July, 2013; v1 submitted 28 August, 2012; originally announced August 2012.

Systematic transcriptome wide analysis of lncRNA-miRNA interactions

Authors: Saakshi Jalali, Deeksha Bhartiya, Vinod Scaria

Abstract: Long noncoding RNAs (lncRNAs) are a recently discovered class of non-protein coding RNAs which have now increasingly been shown to be involved in a wide variety of biological processes as regulatory molecules. Little is known regarding the regulatory interactions between noncoding RNA classes. Recent reports have suggested that lncRNAs could potentially interact with other noncoding RNAs including… ▽ More Long noncoding RNAs (lncRNAs) are a recently discovered class of non-protein coding RNAs which have now increasingly been shown to be involved in a wide variety of biological processes as regulatory molecules. Little is known regarding the regulatory interactions between noncoding RNA classes. Recent reports have suggested that lncRNAs could potentially interact with other noncoding RNAs including miroRNAs (miRNAs) and modulate their regulatory role through interactions. We hypothesized that long noncoding RNAs could participate as a layer of regulatory interactions with miRNAs. The availability of genome-scale datasets for argonaute targets across human transcriptome has prompted us to reconstruct a genome-scale network of interactions between miRNAs and lncRNAs. We used well characterized experimental Photoactivatable-Ribonucleoside-Enhanced Crosslinking and Immunoprecipitation (PAR-CLIP) datasets and the recent genome-wide annotations for lncRNAs in public domain to construct a comprehensive transcriptome-wide map of miRNA regulatory elements. Comparative analysis revealed many of the miRNAs could target long noncoding RNAs, apart from the coding transcripts thus participating in a novel layer of regulatory interactions between noncoding RNA classes. We also find the miRNA regulatory elements have a positional preference, clustering towards the 3' and 5' ends of the long noncoding transcripts. We also further reconstruct a genome-wide map of miRNA interactions with lncRNAs as well as messenger RNAs. This analysis suggests widespread regulatory interactions between noncoding RNAs classes and suggests a novel functional role for lncRNAs. We also present the first transcriptome scale study on lncRNA-miRNA interactions and the first report of a genome-scale reconstruction of a noncoding RNA regulatory interactome involving lncRNAs. △ Less

Submitted 1 August, 2012; originally announced August 2012.

Minimum Complexity Pursuit: Stability Analysis

Authors: Shirin Jalali, Arian Maleki, Richard Baraniuk

Abstract: A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist "universal" algorithms for recovering "structured" si… ▽ More A host of problems involve the recovery of structured signals from a dimensionality reduced representation such as a random projection; examples include sparse signals (compressive sensing) and low-rank matrices (matrix completion). Given the wide range of different recovery algorithms developed to date, it is natural to ask whether there exist "universal" algorithms for recovering "structured" signals from their linear projections. We recently answered this question in the affirmative in the noise-free setting. In this paper, we extend our results to the case of noisy measurements. △ Less

Submitted 21 May, 2012; originally announced May 2012.

Comments: 5 pages, To be presented at ISIT 2012

Minimum Complexity Pursuit

Authors: Shirin Jalali, Arian Maleki

Abstract: The fast growing field of compressed sensing is founded on the fact that if a signal is 'simple' and has some 'structure', then it can be reconstructed accurately with far fewer samples than its ambient dimension. Many different plausible structures have been explored in this field, ranging from sparsity to low-rankness and to finite rate of innovation. However, there are important abstract questi… ▽ More The fast growing field of compressed sensing is founded on the fact that if a signal is 'simple' and has some 'structure', then it can be reconstructed accurately with far fewer samples than its ambient dimension. Many different plausible structures have been explored in this field, ranging from sparsity to low-rankness and to finite rate of innovation. However, there are important abstract questions that are yet to be answered. For instance, what are the general abstract meanings of 'structure' and 'simplicity'? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we aim to address these two questions. Using algorithmic information theory tools such as Kolmogorov complexity, we provide a unified method of describing 'simplicity' and 'structure'. We then explore the performance of an algorithm motivated by Ocam's Razor (called MCP for minimum complexity pursuit) and show that it requires $O(k\log n)$ number of samples to recover a signal, where $k$ and $n$ represent its complexity and ambient dimension, respectively. Finally, we discuss more general classes of signals and provide guarantees on the performance of MCP. △ Less

Submitted 16 October, 2011; originally announced October 2011.

Comments: presented at 2011 Allerton Conference on Communication, Control and Computing

Separation of source-network coding and channel coding in wireline networks

Authors: Shirin Jalali, Michelle Effros

Abstract: In this paper we prove the separation of source-network coding and channel coding in wireline networks. For the purposes of this work, a wireline network is any network of independent, memoryless, point-to-point, finite-alphabet channels used to transmit dependent sources either losslessly or subject to a distortion constraint. In deriving this result, we also prove that in a general memoryless ne… ▽ More In this paper we prove the separation of source-network coding and channel coding in wireline networks. For the purposes of this work, a wireline network is any network of independent, memoryless, point-to-point, finite-alphabet channels used to transmit dependent sources either losslessly or subject to a distortion constraint. In deriving this result, we also prove that in a general memoryless network with dependent sources, lossless and zero-distortion reconstruction are equivalent provided that the conditional entropy of each source given the other sources is non-zero. Furthermore, we extend the separation result to the case of continuous-alphabet, point-to-point channels such as additive white Gaussian noise (AWGN) channels. △ Less

Submitted 17 December, 2012; v1 submitted 16 October, 2011; originally announced October 2011.

Comments: Submitted to the IEEE Transactions on Information Theory

Lossy compression of discrete sources via Viterbi algorithm

Authors: Shirin Jalali, Andrea Montanari, Tsachy Weissman

Abstract: We present a new lossy compressor for discrete-valued sources. For coding a sequence $x^n$, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence $x^n$ an… ▽ More We present a new lossy compressor for discrete-valued sources. For coding a sequence $x^n$, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence $x^n$ and a linear function of its $k^{\rm th}$ order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to recover the minimizer of the cost. We identify a choice of the coefficients comprising the linear function of the empirical distribution used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any stationary ergodic source in the limit of large $n$, provided that $k$ diverges as $o(\log n)$. Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied. △ Less

Submitted 21 November, 2010; v1 submitted 16 November, 2010; originally announced November 2010.

Comments: 26 pages, 6 figures, Submitted to IEEE Transactions on Information Theory

On Equivalence Between Network Topologies

Authors: Michelle Effros, Tracey Ho, Shirin Jalali

Abstract: One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding net… ▽ More One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy. △ Less

Submitted 4 October, 2010; originally announced October 2010.

Comments: 8 pages, 12 figures, 48th Annual Allerton Conference on Communication, Control, and Computing, 2010

On the Separation of Lossy Source-Network Coding and Channel Coding in Wireline Networks

Authors: Shirin Jalali, Michelle Effros

Abstract: This paper proves the separation between source-network coding and channel coding in networks of noisy, discrete, memoryless channels. We show that the set of achievable distortion matrices in delivering a family of dependent sources across such a network equals the set of achievable distortion matrices for delivering the same sources across a distinct network which is built by replacing each ch… ▽ More This paper proves the separation between source-network coding and channel coding in networks of noisy, discrete, memoryless channels. We show that the set of achievable distortion matrices in delivering a family of dependent sources across such a network equals the set of achievable distortion matrices for delivering the same sources across a distinct network which is built by replacing each channel by a noiseless, point-to-point bit-pipe of the corresponding capacity. Thus a code that applies source-network coding across links that are made almost lossless through the application of independent channel coding across each link asymptotically achieves the optimal performance across the network as a whole. △ Less

Submitted 1 May, 2010; originally announced May 2010.

Comments: 5 pages, to appear in the proceedings of 2010 IEEE International Symposium on Information Theory (ISIT)

Multiple Description Coding of Discrete Ergodic Sources

Authors: Shirin Jalali, Tsachy Weissman

Abstract: We investigate the problem of Multiple Description (MD) coding of discrete ergodic processes. We introduce the notion of MD stationary coding, and characterize its relationship to the conventional block MD coding. In stationary coding, in addition to the two rate constraints normally considered in the MD problem, we consider another rate constraint which reflects the conditional entropy of the p… ▽ More We investigate the problem of Multiple Description (MD) coding of discrete ergodic processes. We introduce the notion of MD stationary coding, and characterize its relationship to the conventional block MD coding. In stationary coding, in addition to the two rate constraints normally considered in the MD problem, we consider another rate constraint which reflects the conditional entropy of the process generated by the third decoder given the reconstructions of the two other decoders. The relationship that we establish between stationary and block MD coding enables us to devise a universal algorithm for MD coding of discrete ergodic sources, based on simulated annealing ideas that were recently proven useful for the standard rate distortion problem. △ Less

Submitted 4 November, 2009; originally announced November 2009.

Comments: 6 pages, 3 figures, presented at 2009 Allerton Conference on Communication, Control and Computing

An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources

Authors: Shirin Jalali, Andrea Montanari, Tsachy Weissman

Abstract: We present a new lossy compressor for discrete sources. For coding a source sequence $x^n$, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by a linear combination of its empirical probabilities o… ▽ More We present a new lossy compressor for discrete sources. For coding a source sequence $x^n$, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by a linear combination of its empirical probabilities of some order $k+1$ and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large $n$, provided $k$ is increased as $o(\log n)$. △ Less

Submitted 17 January, 2009; v1 submitted 15 January, 2009; originally announced January 2009.

Comments: 10 pages, 2 figures, Data Compression Conference (DCC) 2009