This paper studies optimal induced-norm state estimation for linear systems subject to norm bounded process noise and measurement errors. A framework based on Information Based Complexity is introduced to generate a set membership interpretation of the l 2 − l 2 and l 2 − l ∞ state estimation problems. This approach leads to an enlightening geometric picture of the problem, allowing for a straightforward derivation of existing results in addition to some new results on suboptimal estimators and limits of performance of optimal induced-norm state smoothers.