We consider the problem of jointly recovering the vector b and the matrix C from noisy measurementsY=A(b)C+W , where A(⋅) is a known affine linear function of b (i.e., A(b)=A0 +∑Qi=1biAi with known matrices Ai ). This problem has applications in matrix completion, robust PCA, dictionary learning, self-calibration, blind deconvolution, joint-channel/symbol estimation, compressive sensing with matrix uncertainty, and many other tasks.