A novel stochastic algorithm is presented for estimating Atmospheric Infrared Sounder (AIRS) radiances in the 3.7--15.4 micron spectral band that would be observed from space in the absence of clouds. This algorithm examines 3 ¿ 3 sets of 15-km AIRS fields of view, selects the clearest fields, and then estimates a single cloud-cleared infrared spectrum for the 3 ¿ 3 set using a series of simple linear and nonlinear operations on both the infrared and companion Advanced Microwave Sounding Unit (AMSU) microwave channels. These instruments were launched on the NASA Aqua satellite in May 2002. The algorithm was both trained and tested within 70¿ of the equator using global numerical weather analyses generated by the European Center for Medium-range Weather Forecasts (ECMWF); these analyses were converted to radiances using the SARTA v1.05 equation of radiative transfer. The RMS differences between the AIRS 4- and 15-micron CO2-band observations and the corresponding ECMWF/SARTA radiances over nighttime ocean are ~0.2--0.3 K for ~60 selected channels with weighting functions peaking at tropospheric altitudes down to the surface for the best 28% of all soundings selected using only AIRS data. For a larger ensemble of 314 channels the corresponding range was 0.27--0.40 K. Latitudes 30--70¿ yielded RMS differences of 0.26--0.78 K over land at night for the same 314 channels. Mean differences were largely eliminated by training the estimates using independent global observations made on the same 3 test days, which were spaced over 2 months.