Transient analysis of large-scale power delivery network (PDN) is a critical task to ensure the functional correctness and desired performance of today's integrated circuits (ICs), especially if significant transient noises are induced by clock and/or power gating due to the utilization of extensive power management. In this paper, we propose an efficient algorithm for PDN transient analysis based on sparse approximation. The key idea is to exploit the fact that the transient response caused by clock/power gating is often localized and the voltages at many other "inactive" nodes are almost unchanged, thereby rendering a unique sparse structure. By taking advantage of the underlying sparsity of the solution structure, a modified conjugate gradient algorithm is developed and tuned to efficiently solve the PDN analysis problem with low computational cost. Our numerical experiments based on standard benchmarks demonstrate that the proposed transient analysis with sparse approximation offers up to 2.2× runtime speedup over other traditional methods, while simultaneously achieving similar accuracy.