# Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems

arXiv: https://arxiv.org/abs/2302.08781 · HTML: https://mlsanity.com/paper/2302.08781/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2023.

## Built on by (most cited first, 2 of 2)

- [Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading](https://mlsanity.com/paper/2509.06466/) (2025)
- [Interpolation Conditions for Data Consistency and Prediction in Noisy Linear Systems](https://mlsanity.com/paper/2504.08484/) (2025)

## Abstract (arXiv)

The Performance Estimation Problem methodology makes it possible to determine the exact worst-case performance of an optimization method. In this work, we generalize this framework to first-order methods involving linear operators. This extension requires an explicit formulation of interpolation conditions for those linear operators. We consider the class of linear operators M:x mapsto Mx where matrix M has bounded singular values, and the class of linear operators where M is symmetric and has bounded eigenvalues. We describe interpolation conditions for these classes, i.e. necessary and sufficient conditions that, given a list of pairs (xi,yi), characterize the existence of a linear operator mapping xi to yi for all i. Using these conditions, we first identify the exact worst-case behavior of the gradient method applied to the composed objective hcirc M, and observe that it always corresponds to M being a scaling operator. We then investigate the Chambolle-Pock method applied to f+gcirc M, and improve the existing analysis to obtain a proof of the exact convergence rate of the primal-dual gap. In addition, we study how this method behaves on Lipschitz convex functions, and obtain a numerical convergence rate for the primal accuracy of the last iterate. We also show numerically that averaging iterates is beneficial in this setting.