For wireless multimedia sensor networks, in the radio channel there exist random fading, high error rate and other issues, especially on video applications. Applying the compressed sensing theory to video encoding provides an approach to resist random wireless channel fading and reduce error rate. However, the high complexity of compressed sensing reconstruction algorithm makes it difficult to recover the real-time video sequences at the decoder. Here, by improving iterative search algorithm, iterative search method and the loop termination conditions, a fast and efficient smoothed l0 norm-based video decoding compressed sensing algorithm (ADSL0) is presented. To ensure the optimal iteration path, the algorithm uses a strict descent direction and correction iterative step. Experimental results show that the proposed algorithm in terms of time-consumingre modeling or reconstruction accuracy is significantly better than other similar algorithms.