We present a new framework for fast edge-aware processing of images and videos. The proposed smoothing method is based on an optimization formulation with a non-convex sparse regularization for a better smoothing behavior near strong edges. We develop mathematical tools based on first order approximation of proximal operators to accelerate the proposed method while maintaining high-quality smoothing. The first order approximation is used to estimate a solution of the proximal form in a half-quadratic solver, and also to derive a warm-start solution that can be calculated quickly when the image is loaded by the user. We extend the method to large-scale processing by estimating the smoothing operation with independent 1D convolution operations. This approach linearly scales to the size of the image and can fully take advantage of parallel processing. The method supports full color filtering and turns out to be temporally coherent for fast video processing. We demonstrate the performance of the proposed method on various applications including image smoothing, detail manipulation, HDR tone-mapping, fast edge simplification and video edge-aware processing.