This work is concerned with approximating the smallest eigenvalue of a parameter-dependent Hermitian matrix A(μ) for many parameter values μ ∈ RP. The design of reliable and efficient algorithms for addressing this task is of importance in a variety of applications. Most notably, it plays a crucial role in estimating the error of reduced basis methods for parametrized partial differential equations. The current state-of-the-art approach, the so called Successive Constraint Method (SCM), addresses affine linear parameter dependencies by combining sampled Rayleigh quotients with linear programming techniques. In this work, we propose a subspace approach that additionally incorporates the sampled eigenvectors of A(μ) and implicitly exploits their smoothness properties. Like SCM, our approach results in rigorous lower and upper bounds for the smallest eigenvalues on D. Theoretical and experimental evidence is given to demonstrate that our approach represents a significant improvement over SCM in the sense that the bounds are often much tighter, at negligible additional cost.