← ALL STATEMENTS
AcceptedProposition · Statement with omitted proof

Spectral norm of a positive semidefinite block matrix

The diagonal block norms bound the norm of a positive semidefinite block matrix.

Halko, Martinsson & Tropp ↗
Source label: prop:spec-norm-sum

Formal statement. The assumptions and conclusion are explicit; the theorem proof is omitted (sorry).

01 / MATHEMATICAL STATEMENT

Meaning & conditions

Mathematical summary

The diagonal block norms bound the norm of a positive semidefinite block matrix.

∥[ABB∗C]∥≤∥A∥+∥C∥\left\|\begin{bmatrix}A&B\\B^*&C\end{bmatrix}\right\|\le\|A\|+\|C\|

Assumptions & context

  • The block matrix with diagonal blocks A,C and off-diagonal blocks B,B* is positive semidefinite.

Source

Halko, Martinsson & Tropp. Finding structure with randomness.

Source label: prop:spec-norm-sum

02 / LEAN REPRESENTATION

Formal statement

Statement with omitted proof. Expand the complete file below to read imports, local definitions and surrounding context.

theorem spec_norm_sum_of_psd_partitioned
    {𝕜 : Type*} [RCLike 𝕜]
    {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
    (A : Matrix m m 𝕜) (B : Matrix m n 𝕜) (C : Matrix n n 𝕜)
    (hM : (Matrix.fromBlocks A B Bᴴ C).PosSemidef) :
    ‖Matrix.fromBlocks A B Bᴴ C‖ ≤ ‖A‖ + ‖C‖ := by
  sorry
Complete Lean file and local definitions
import RNLAPhaseB.B3Base
import RNLAPhaseB.Complexity

open MeasureTheory
open scoped Matrix
open scoped Matrix.Norms.L2Operator
open scoped BigOperators
open scoped ENNReal
open scoped ComplexOrder

namespace RNLAPhaseB.HMT2011.SpecNormSum

/-- HMT Proposition (prop:spec-norm-sum): for each partitioned psd matrix
`M = [[A, B], [B^*, C]]`, the spectral norm satisfies `‖M‖ ≤ ‖A‖ + ‖C‖`.

`‖·‖` is the spectral (ℓ₂ operator) norm, via the scoped instance
`Matrix.Norms.L2Operator`. The partitioned matrix is `Matrix.fromBlocks A B Bᴴ C`,
where `Bᴴ` is the conjugate transpose (the source's `B^*`). "psd" is
`Matrix.PosSemidef`, which includes Hermitian-ness. It uses the standard `ComplexOrder`
partial order on the `RCLike` scalars, so `0 ≤ x^* M x` means the quadratic form is real
and nonnegative. The scalar field is any `RCLike` field, which covers both the real and
the complex case. The block sizes are arbitrary finite index types. -/
theorem spec_norm_sum_of_psd_partitioned
    {𝕜 : Type*} [RCLike 𝕜]
    {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
    (A : Matrix m m 𝕜) (B : Matrix m n 𝕜) (C : Matrix n n 𝕜)
    (hM : (Matrix.fromBlocks A B Bᴴ C).PosSemidef) :
    ‖Matrix.fromBlocks A B Bᴴ C‖ ≤ ‖A‖ + ‖C‖ := by
  sorry

end RNLAPhaseB.HMT2011.SpecNormSum

How to read the formalization

  • The hypothesis concerns the whole block matrix, not only its diagonal blocks.
← Back to all statements