Computing the Lipschitz constant needed for fast scene recovery from CASSI measurements

The linear inverse problem associated with the standard model for hyperspectral image recovery from CASSI measurements is considered. This is formulated as the minimization of an objective function which is the sum of a total variation regularizer and a least squares loss function. Standard first-order iterative minimization algorithms, such as ISTA, FISTA and TwIST, require as input the value of the Lipschitz constant for the gradient of the loss function, or at least a good upper bound on this value, in order to select appropriate step lengths. For the loss term considered here, this Lipschitz constant equals the square of the largest singular value of the measurement map. In applications, this singular value is usually computed directly as the largest eigenvalue of a huge square matrix. This computation can sometimes be a bottleneck in an otherwise optimized algorithm. In this paper we effectively eliminate this bottleneck for CASSI reconstructions by showing how the Lipschitz constant can be calculated from a square matrix whose size is easily three orders of magnitudes smaller than in the direct approach.