zbMATH — the first resource for mathematics

Efficient blind search: optimal power of detection under computational cost constraints. (English) Zbl 1161.62087
Summary: Some astronomy projects require a blind search through a vast number of hypotheses to detect objects of interest. The number of hypotheses to test can be in the billions. A naive blind search over every single hypothesis would be far too costly computationally. We propose a hierarchical scheme for blind search, using various “resolution” levels. At lower resolution levels, “regions” of interest in the search space are singled out with a low computational cost. These regions are refined at intermediate resolution levels and only the most promising candidates are finally tested at the original fine resolution. The optimal search strategy is found by dynamic programming. We demonstrate the procedure for pulsar search from satellite gamma-ray observations and show that the power of the naive blind search can almost be matched with the hierarchical scheme while reducing the computational burden by more than three orders of magnitude.

62P35 Applications of statistics to physics
85A35 Statistical astronomy
90C39 Dynamic programming
90C90 Applications of mathematical programming
85A05 Galactic and stellar dynamics
Full Text: DOI
[1] Abramovici, A., Althouse, W., Drever, R., Gursel, Y., Kawamura, S., Raab, F., Shoemaker, D., Sievers, L., Spero, R., Thorne, K. et al. (1992). LIGO: The laser interferometer gravitational-wave observatory. Science 256 325.
[2] Alcock, C., Dave, R., Giammarco, J., Goldader, J., Lehner, M., King, S., Lee, T., Wang, A., Wang, S., Wen, C. et al. (2003). TAOS: The Taiwanese-American occultation survey. Earth, Moon and Planets 92 459-464.
[3] Bertsekas, D. (1995). Dynamic Programming and Optimal Control . Athena Scientific. · Zbl 0904.90170
[4] Bickel, P., Kleijn, B. and Rice, J. (2007a). Event weighted tests for detecting periodicity in photon arrival times. Astrophysical J.
[5] Bickel, P., Kleijn, B. and Rice, J. (2007b). On detecting periodicity in astronomical point processes. In Challenges in Modern Astronomy IV (J. Babu and E. Feigelson, eds.). ASP Conference Series 371 305-320.
[6] Bickel, P. and Yahav, J. (1967). Asymptotically pointwise optimal procedures in sequential analysis. Proc. Fifth Berk. Symp. Math. Statist. Probab. 1 401-413. Univ. California Press, Berkeley. · Zbl 0214.45105
[7] Blanchard, G. and Geman, D. (2005). Hierarchical testing designs for pattern recognition. Ann. Statist. 33 1155-1202. · Zbl 1072.62052
[8] Brady, P. and Creighton, T. (2000). Searching for periodic sources with LIGO. II. Hierarchical searches. Phys. Rev. D 61 82001.
[9] Chandler, A., Koh, D., Lamb, R., Macomb, D., Mattox, J., Prince, T. and Ray, P. (2001). A search for radioquiet gammaray pulsars. Astrophysical J. 556 59-69.
[10] Cutler, C., Gholami, I. and Krishnan, B. (2005). Improved stack-slide searches for gravitational-wave pulsars. Phys. Rev. D 72 42004.
[11] Danzmann, K. et al. (1996). LISA: Laser interferometer space antenna for gravitational wave measurements. Classical and Quantum Gravity 13 A247-A250.
[12] Dorfman, R. (1943). The detection of defective members of large populations. Ann. Math. Statist. 14 436-440.
[13] Gehrels, N. and Michelson, P. (1999). GLAST: The next-generation high-energy gamma-ray astronomy mission. Astroparticle Physics 11 277.
[14] Hartman, R., Bertsch, D., Bloom, S., Chen, A., Deines-Jones, P., Esposito, J., Fichtel, C., Friedlander, D., Hunter, S., McDonald, L., Sreekumar, P., Thompson, D., Jones, B., Lin, Y., Michelson, P., Nolan, P., Tompkins, W., Kanbach, G., Mayer-Hasselwander, H., Mücke, A., Pohl, M., Reimer, O., Kniffen, D., Schneid, E., von Montigny, C., Mukherjee, R. and Dingus, B. (1999). The third EGRET catalog of high-energy gamma-ray sources. Astrophysical J. Suppl. Ser. 123 79-202.
[15] Kaiser, N., Aussel, H., Burke, B., Boesgaard, H., Chambers, K., Chun, M., Heasley, J., Hodapp, K., Hunt, B. and Jedicke, R. (2002). Pan-STARRS: A large synoptic survey telescope array. Proceedings of SPIE 4836 154-164.
[16] Kanbach, G., Bertsch, D., Favale, A., Fichtel, C., Hartman, R., Hofstadter, R., Hughes, E., Hunter, S., Hughlock, B., Kniffen, D. et al. (1989). The project EGRET (energetic gamma-ray experiment telescope) on NASA’s gamma-ray observatory GRO. Space Science Reviews 49 69-84.
[17] Kiefer, J. and Sacks, J. (1963). Asymptotically optimum sequential inference and design. Ann. Math. Statist. 34 705-750. · Zbl 0255.62063
[18] Mardia, K. and Jupp, P. (1999). Directional Statistics . Wiley, New York. · Zbl 0935.62065
[19] Ransom, S., Eikenberry, S. and Middleditch, J. (2002). Fourier techniques for very long astrophysical time-series analysis. Astronomical J. 124 1788-1809.
[20] Tyson, J. (2002). Large synoptic survey telescope-overview. In Proc. SPIE 4836 10-20.
[21] Viola, P. and Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. In Proc. CVPR 1 511-518.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.