The Experts below are selected from a list of 303 Experts worldwide ranked by ideXlab platform
Abbas El Gamal - One of the best experts on this subject based on the ideXlab platform.
-
strong Functional Representation lemma and applications to coding theorems
IEEE Transactions on Information Theory, 2018Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong Functional Representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem.
-
Strong Functional Representation Lemma and Applications to Coding Theorems
IEEE Transactions on Information Theory, 2018Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z|Y) ≤ log(I(X; Y)+1)+4 bits. We use this strong Functional Representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray-Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem.
-
Strong Functional Representation lemma and applications to coding theorems
2017 IEEE International Symposium on Information Theory (ISIT), 2017Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong Functional Representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.
-
ISIT - Strong Functional Representation lemma and applications to coding theorems
2017 IEEE International Symposium on Information Theory (ISIT), 2017Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong Functional Representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.
Cheuk Ting Li - One of the best experts on this subject based on the ideXlab platform.
-
A Unified Framework for One-shot Achievability via the Poisson Matching Lemma
2019 IEEE International Symposium on Information Theory (ISIT), 2019Co-Authors: Cheuk Ting Li, Venkat AnantharamAbstract:We introduce the Poisson matching lemma and apply it to prove one-shot achievability results for channels with state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, and distributed lossy source coding. Our one-shot bounds improve upon the best known bounds in the aforementioned settings, with shorter proofs in some settings even when compared to the conventional asymptotic typicality approach. The Poisson matching lemma replaces both the packing and covering lemmas. This paper extends the work of Li and El Gamal on Poisson Functional Representation for variable-length source coding settings, showing that the Poisson Functional Representation is a viable alternative to typicality for most problems in network information theory.
-
strong Functional Representation lemma and applications to coding theorems
IEEE Transactions on Information Theory, 2018Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong Functional Representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem.
-
Strong Functional Representation Lemma and Applications to Coding Theorems
IEEE Transactions on Information Theory, 2018Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z|Y) ≤ log(I(X; Y)+1)+4 bits. We use this strong Functional Representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray-Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem.
-
Strong Functional Representation lemma and applications to coding theorems
2017 IEEE International Symposium on Information Theory (ISIT), 2017Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong Functional Representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.
-
ISIT - Strong Functional Representation lemma and applications to coding theorems
2017 IEEE International Symposium on Information Theory (ISIT), 2017Co-Authors: Cheuk Ting Li, Abbas El GamalAbstract:This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong Functional Representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.
Qi Yu - One of the best experts on this subject based on the ideXlab platform.
-
EFFICIENT LARGE-SCALE SERVICE CLUSTERING VIA SPARSE Functional Representation AND ACCELERATED OPTIMIZATION
International Journal of Cooperative Information Systems, 2020Co-Authors: Qi YuAbstract:Clustering techniques offer a systematic approach to organize the diverse and fast increasing Web services by assigning relevant services into homogeneous service communities. However, the ever increasing number of Web services poses key challenges for building large-scale service communities. In this paper, we tackle the scalability issue in service clustering, aiming to accurately and efficiently discover service communities over very large-scale services. A key observation is that service descriptions are usually represented by long but very sparse term vectors as each service is only described by a limited number of terms. This inspires us to seek a new service Representation that is economical to store, efficient to process, and intuitive to interpret. This new Representation enables service clustering to scale to massive number of services. More specifically, a set of anchor services are identified that allows each service to represent as a linear combination of a small number of anchor services. In this way, the large number of services are encoded with a much more compact anchor service space. Despite service clustering can be performed much more efficiently in the compact anchor service space, discovery of anchor services from large-scale service descriptions may incur high computational cost. We develop principled optimization strategies for efficient anchor service discovery. Extensive experiments are conducted on real-world service data to assess both the effectiveness and efficiency of the proposed approach. Results on a dataset with over 3,700 Web services clearly demonstrate the good scalability of sparse Functional Representation and the efficiency of the optimization algorithms for anchor service discovery.
-
ICSOC - Sparse Functional Representation for large-scale service clustering
Service-Oriented Computing, 2012Co-Authors: Qi YuAbstract:Service clustering provides an effective means to discover hidden service communities that group services with relevant Functionalities. However, the ever increasing number of Web services poses key challenges for building large-scale service communities. In this paper, we address the scalability issue in service clustering, aiming to discover service communities over very large-scale services. A key observation is that service descriptions are usually represented by long but very sparse term vectors as each service is only described by a limited number of terms. This inspires us to seek a new service Representation that is economical to store, efficient to process, and intuitive to interpret. This new Representation enables service clustering to scale to massive number of services. More specifically, a set of anchor services are identified that allow to represent each service as a linear combination of a small number of anchor services. In this way, the large number of services are encoded with a much more compact anchor service space. We conduct extensive experiments on real-world service data to assess both the effectiveness and efficiency of the proposed approach. Results on a dataset with over 3,700 Web services clearly demonstrate the good scalability of sparse Functional Representation.
B Chandrasekaran - One of the best experts on this subject based on the ideXlab platform.
-
representing function relating Functional Representation and Functional modeling research streams
Ai Edam Artificial Intelligence for Engineering Design Analysis and Manufacturing, 2005Co-Authors: B ChandrasekaranAbstract:This paper is an informal description of some recent insights about what a device function is, how it arises in response to needs, and how function arises from the structure of a device and the functions of its components. These results formalize and clarify a set of contending intuitions about function that researchers have had. The paper relates the approaches, results, and goals of this stream of research, called Functional Representation (FR), with the Functional modeling (FM) stream in engineering. Despite the occurrence of the term function in the two streams, often the results and techniques in the two streams appear not to have much to do with each other. I argue that, in fact, the two streams are performing research that is mutually complementary. FR research provides the basic layer for device ontology in a formal framework that helps to clarify the meanings of terms such as function and structure, and also to support Representation of device knowledge for automated reasoning. FM research provides another layer in device ontology, by attempting to identify behavior primitives that are applicable to subsets of devices, with the hope that functions can be described in those domains with an economy of terms. This can lead to useful catalogs of functions and devices in specific areas of engineering. With increased attention to formalization, the work in FM can provide domain-specific terms for FR research in knowledge Representation and automated reasoning.
-
Functional Representation of Software Systems and Component-Based Software Technology
1998Co-Authors: B Chandrasekaran, Bruce WeideAbstract:Abstract : The overall objectives of this project were to develop approaches to program comprehension that would provide significant added benefits in many aspects of software engineering. As one part of that effort, the RESOLVE/ACTI framework for a software component composition technology was developed. The technology focuses on development of software components that can be reused and a composition discipline that helps in creating programs whose properties can be efficiently reasoned about. As another part of the effort, a device comprehension framework called Functional Representation was applied, and its utility shown for software architecture comprehension, legacy software reengineering and Representation of system requirements.
-
CAUSAL Functional Representation LANGUAGE WITH BEHAVIOR-BASED SEMANTICS
Applied Artificial Intelligence, 1995Co-Authors: Yumi Iwasaki, Marcos Vescovi, Richard Fikes, B ChandrasekaranAbstract:Understanding the design of a device requires both knowledge of the general physical principles that determine its behavior and knowledge of its intended functions. However, the majority of work in model-based reasoning has focused on using either one of these types of knowledge alone. In order to use both types of knowledge in understanding a device design, one must represent the Functional knowledge in such a way that it has a clear interpretation in terms of observed behavior. We propose a new formalism, causal Functional Representation language (CFRL),for representing device functions with well-defined semantics in terms of behavior. CFRL allows the specification of conditions that a behavior must satisfy, such as occurrence of temporal sequences of events and causal relations among them and the components. We have used CFRL as the basis for aFunctional verification program, which determines whether a behavior achieves an intended function.
-
Functional Representation: A BRIEF HISTORICAL PERSPECTIVE
Applied Artificial Intelligence, 1994Co-Authors: B ChandrasekaranAbstract:Abstract I review research in the last decade in the framework called Functional Representation (FR). FR is a language for describing the function of a device, its structure, and the causal processes in the device that culminate in the achievement of the function. The causal transitions are annotated in specific ways that explain the role of the functions of the components and domain laws in the achievement of various states and, hence, the function of the device. I describe the uses of FR for simulation, diagnosis, and design, among other tasks.
-
Functional Representation and causal processes
Advances in Computers, 1994Co-Authors: B ChandrasekaranAbstract:Publisher Summary This chapter discusses a theory of Representation of causal processes and uses the Representational framework for problem solving of various sorts. It presents a framework for thinking about human reasoning about the physical world, and describes the role played by causal process packages in this framework. The chapter gives an informal overview of Functional Representation (FR) and mentions that FR for a device has three parts: a description of intended function, a description of the structure of the device, and a description of the way the device achieves the function. It lists the component names and their functions and indicates the way the components are put together to make the device. The basic idea in describing the way a device achieves its function is that of a causal process description (CPD). Various applications of FR are reviewed. The organization of a Functional Representation gives both forward and backward reasoning capability. The chapter describes an algorithm that demonstrates the forward simulation potential.
Ron D. Frostig - One of the best experts on this subject based on the ideXlab platform.
-
Quantitative long-term imaging of the Functional Representation of a whisker in rat barrel cortex (sensory Representationyvibrissaeyintrinsic signalsyoptical imaging)
1996Co-Authors: Susan A. Masino, Ron D. FrostigAbstract:In this study, we implement chronic optical imaging of intrinsic signals in rat barrel cortex and repeatedly quantify the Functional Representation of a single whisker over time. The success of chronic imaging for more than 1 month enabled an evaluation of the normal dynamic range of this sensory Representation. In individual animals for a period of several weeks, we found that: (i) the average spatial extent of the quantified Functional Representation of whisker C2 is surprisingly large—1.71 mm 2 (area at half-height); (ii) the location of the Functional Representation is consistent; and (iii) there are ongoing but nonsystematic changes in spatio- temporal characteristics such as the size, shape, and response amplitude of the Functional Representation. These results support a modified description of the Functional organization of barrel cortex, where although a precisely located module corresponds to a specific whisker, this module is dynamic, large, and overlaps considerably with the modules of many other whiskers.
-
Quantitative long-term imaging of the Functional Representation of a whisker in rat barrel cortex.
Proceedings of the National Academy of Sciences of the United States of America, 1996Co-Authors: Susan A. Masino, Ron D. FrostigAbstract:Abstract In this study, we implement chronic optical imaging of intrinsic signals in rat barrel cortex and repeatedly quantify the Functional Representation of a single whisker over time. The success of chronic imaging for more than 1 month enabled an evaluation of the normal dynamic range of this sensory Representation. In individual animals for a period of several weeks, we found that: (i) the average spatial extent of the quantified Functional Representation of whisker C2 is surprisingly large--1.71 mm2 (area at half-height); (ii) the location of the Functional Representation is consistent; and (iii) there are ongoing but nonsystematic changes in spatiotemporal characteristics such as the size, shape, and response amplitude of the Functional Representation. These results support a modified description of the Functional organization of barrel cortex, where although a precisely located module corresponds to a specific whisker, this module is dynamic, large, and overlaps considerably with the modules of many other whiskers.
