In the robust stability analysis of linear time invariant systems, the frequency domain and uncertainty domain of interest play algebraically symmetric roles. This paper presents a new formulation of the S-procedure and the KYP lemma which emphasizes this symmetry. The new formulation provides a novel and unified approach for understanding when the KYP lemma provides an exact LMI test for robust stability. The notions of weak and strong mutual losslessness are introduced to characterize lossless S-procedure and KYP lemma. The new formulation has sufficient flexibility to accommodate some recent extensions of the KYP lemma, including the Generalized KYP lemma, the KYP lemma for nD systems, and the diagonal bounded real lemma for internally positive systems. Using the proposed framework, we also provide a lossless scaled small gain test for internally positive systems which gives an alternative proof that the structured singular value for such systems with arbitrary number of scalar uncertainties can be efficiently computed.