This paper introduces an alternative formulation of the Kalman-Yakubovich-Popov (KYP) Lemma, relating an infinite dimensional Frequency Domain Inequality (FDI) to a pair of finite dimensional Linear Matrix Inequalities (LMI). It is shown that this new formulation encompasses previous generalizations of the KYP Lemma which hold in the case the coefficient matrix of the FDI does not depend on frequency. In addition, it allows the coefficient matrix of the frequency domain inequality to vary affinely with the frequency parameter. One application of this results is illustrated in an example of computing upper bounds to the structured singular value with frequency-dependent scalings. (C) 2009 Elsevier Ltd. All rights reserved.