Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

AVERAGE CASE I-COMPLEXITY IN COMPUTER SCIENCE A BAYESIAN VIEW

IP.com Disclosure Number: IPCOM000127974D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 13 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

J. B. Kadane: AUTHOR [+4]

Abstract

Relations between average case e -complexity and Bayesian statistics are discussed. An algorithm corresponds to a decision function. and the choice of information to the choice of an experiment. Adaptive information in e-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving iF-complexity and minimax-Bayesian interpretations for factor analysis. Results from i-complexity are used to establish that the optimal sequential design is no better than optimal nonsequential design for that problem. I This paper shows that average case analysis of algorithms and information in ' -Complexity theory is related to to optimal decisions and experiments, respectively, in Bayesian Theory. Finding such relations betweom problems in previously disjoint literatures is exciting both because one discovers a new set of colleagues and because results obtained in each literature can illuminate the other. Sections I and 2 explain, respectively, the worst-case and average-case analysis of algorithms. Section 3 establishes the correspondence mentioned above. Finally, Section 4 discusses some results from the average case e -complexity literature, and its interpretation for Bayesians. We hope that the relation reported here can lead to further fruitful results for both fields.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AVERAGE CASE I-COMPLEXITY IN COMPUTER SCIENCE A BAYESIAN VIEW

July 1983

J. B. Kadane Carnegie-Mellon University G. W. Wasilkowski Columbia University

TABLE OF CONTENTS

I Worst Case Analysis 3 2 Average Case Anaysis 6

3 A Bayesian Interpretation of the Average Case Model 12

4 An Application to Factor Analysis is 5 Conclusion 20

Acknowledgements

The authors are grateful to H. T. Kung, M. 1. Shainos and J. F. Traub for their roles in bringing them together. Joseph B. Kadane was supported in part by ONR Contract 014-82-K-0622 and
G. W. Wasilkowski was supported in part by the National Science Foundation under Grant MCS-7823676.

Abstract

Relations between average case e -complexity and Bayesian statistics are discussed. An algorithm corresponds to a decision function. and the choice of information to the choice of an experiment. Adaptive information in e-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving iF-complexity and minimax-Bayesian interpretations for factor analysis. Results from i-complexity are used to establish that the optimal sequential design is no better than optimal nonsequential design for that problem.

This paper shows that average case analysis of algorithms and information in ' -Complexity theory is related to to optimal decisions and experiments, respectively, in Bayesian Theory. Finding such relations betweom problems in previously disjoint literatures is exciting both because one discovers a new set of colleagues and because results obtained in each literature can illuminate the other.

Sections I and 2 explain, respectively, the worst-case and average-case analysis of algorithms. Section 3 establishes the correspondence mentioned above. Finally, Section 4 discusses some results from the average case e -complexity literature, and its interpretation for Bayesians. We hope that the relation reported here can lead to further fruitful results for both fields.

I Worst Case Analysis

Columbia University Page 1 Dec 31, 1983

Page 2 of 13

AVERAGE CASE I-COMPLEXITY IN COMPUTER SCIENCE A BAYESIAN VIEW

In this section we briefly present some major questions addressed in F -complexity theory. We first discuss the worst case model which is conceptually simpler than the average case model, discussed in Section 2.

An expository account of i -complexity theory (which is also known as information- centered kowski (1983). The general worst case model is theory) may be found in Traub and Wozn1a presented iu two research monographs: Traub and Woz'niakowski (1980) and Traub, Wasilkowski and Wozniakowski (1983). The first of these has an extensive annotated bibliography. Reports on the average case model are cited in Section 2.

A simple integration problem provides a suggestive illustration. We wish to approximate

f(t)dt knowing n values of f at points ti, N(f) - EM I f (t and knowing that f belongs to a given class F of...