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 E-COMPLEXITY IN COMPUTER SCIENCE: A BAYESIAN VIEW

IP.com Disclosure Number: IPCOM000148346D
Original Publication Date: 1983-Jul-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Kadane, J.B.: AUTHOR [+3]

Abstract

AVERAGE CASE €-COMPLEXITY IN COMPUTER, SCIENCE : A BAYESIAN VIEW July 1983 J. 8. Kadane Carnegle-Mellon Unlvers~ty G. W. Wasilkowski Columb~a University TABLE OF CONTENTS 1 Worst Case Analysis 2 Averagc Case Anaysis 3 A Bayesian Interpretation of the Average Case Model 4 An Application to Factor Analysis 5 Conciuslon Acknowledgements Tht authors are grateful to H. T, Kung, M. I. Shainos and J. F. Traub for the~r 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 Foundat~on under Grant MCS-7823676. Abstract Relations between average case t -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 6-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving 6-complexity and minimax-Bayesian interpretations for factor analysis. Results from 6-complexity are used to establish that t k optimal sequential design is no better than optimal nonsequential design for that problem.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 24

AVERAGE CASE €-COMPLEXITY
IN COMPUTER, SCIENCE :

A BAYESIAN VIEW

July 1983
J. 8. Kadane Carnegle-Mellon Unlvers~ty
G. W. Wasilkowski Columb~a University

[This page contains 1 picture or other non-text object]

Page 2 of 24

TABLE OF CONTENTS

1 Worst Case Analysis


2 Averagc Case Anaysis


3 A Bayesian Interpretation of the Average Case Model

4 An Application to Factor Analysis


5 Conciuslon

[This page contains 1 picture or other non-text object]

Page 3 of 24

Acknowledgements

Tht authors are grateful to H. T, Kung, M. I. Shainos and J. F. Traub for the~r 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 Foundat~on under Grant MCS-7823676.

[This page contains 1 picture or other non-text object]

Page 4 of 24

Abstract

Relations between average case t -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 6-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving 6-complexity and minimax-Bayesian interpretations for factor analysis. Results from 6-complexity are used to establish that t k optimal sequential design is no better than optimal nonsequential design for that problem.

[This page contains 1 picture or other non-text object]

Page 5 of 24

This paper shows that average case analysis of algorithms and Information in c-complexity theory is related to to optimal decisions and experiments, respectively. in Bayesian Theory. Finding such relations betwwn 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 1 and 2 explain, respectively. the worst-case and averagccase analysls of algorithms. Section 3 establishes t h correspondence mentioned abave. Finally, Sectlon 4 hscusses some results from the average case c-complexity literature, and ~ t s mterpretation for Bayesians. We hope that the relatlon reported here can lead to further fruitful results for both fields.

1 Worst Case Analysis

in ths section we briefly present some major quest~ons addressed tn c-complexity theory. We

first ducuss the worst case model wkch is concr?ptually simpler than tbc average case model, discussed ln Sectlon 2.

An expository account of c -complexity theory (wtuch ~s also known as informat~on-centered

theory) may be found m Traub and ~oz'ntakowski (1983). T k general worst case model u
presented u two research monographs: Traub and ~oz&rakowski

                                                      ( 1980) and Traub, Was~lkowsk~ and ~o&akowski (1983). T k first of these has an extensive annotated blbllography. Reports
on the average case model are cited in Section 2.

A...