Signed vector-spin objectives and low-rank Gram factors

Let $n,r\ge 1$ be integers and let $B=(B_{ij})$ be a real symmetric $n\times n$ matrix. A vector-spin configuration is a matrix $Y\in {\mathbb{R}}^{n\times r}$ whose rows $u_1,\dots ,u_n\in {\mathbb{R}}^r$ are unit vectors for the Euclidean inner product: $u_i\cdot u_i=1$. Its signed vector-spin objective is $F_B(Y)=\mathrm{Tr}(Y^{T}BY)$. The entries of $B$ may have either sign.

The Gram matrix of the configuration is $X=Y{Y}^T$, with $X_{ij}=u_i\cdot u_j$. A real symmetric matrix $X$ is positive semidefinite if $c^{T}Xc\ge 0$ for every $c\in {\mathbb{R}}^n$. The factor $Y$ has at most $r$ columns; using $X=Y{Y}^T$ with unit rows of $Y$ as a parametrization of a positive semidefinite matrix variable with diagonal entries one is a Burer–Monteiro factorization. It imposes the rank bound $\mathrm{rank}X\le r$.

Identify matrices with ${\mathbb{R}}^{nr}$ by listing their entries. The feasible set is $M_{n,r}=\{Y\in {\mathbb{R}}^{n\times r}:u_i\cdot u_i=1\text{ for every }i\}$, with the relative Euclidean topology and the smooth structure of the regular level set of $Q:{\mathbb{R}}^{nr}\to {\mathbb{R}}^n$, $Q(Y)=(u_i\cdot u_i{)}_{i=1}^n$, at $(1,\dots ,1)$. Its dimension is $n(r-1)$ and its tangent space is $T_Y{M}_{n,r}=\{V=(v_i{)}_{i=1}^n:u_i\cdot v_i=0\text{ for every }i\}$. The objective is smooth in this structure.

A feasible $Y$ is a local minimum of $F_B$ when there is $\epsilon >0$ such that $F_B(Y)\le F_B(Z)$ for every feasible $Z$ with ${\sum }_{i=1}^n{\sum }_{a=1}^r(Z_{ia}-Y_{ia}{)}^2<{\epsilon }^2$. A local maximum reverses the inequality; a local extremum is either. A critical point is a feasible $Y$ for which the differential $d(F_B{)}_Y:T_Y{M}_{n,r}\to \mathbb{R}$ is the zero linear functional. For $r=1$, $M_{n,1}=\{-1,1{\}}^n$ is discrete with zero-dimensional tangent spaces: every configuration is critical and is both a local minimum and a local maximum.

The Euclidean inner product ⟨ x,y⟩ = ∑_k<n xₖ yₖ on ℝⁿ

The Gram matrix G(v₀,…,vᵣ₋₁)=(⟨ vᵢ,vⱼ⟩)_i,j<r and Gram determinant, with empty value 1

Rectangular matrix multiplication and the identity matrix Iₙ, including zero-sized shapes

Row space, column space, nullspace, row rank, column rank and matrix rank

The trace tr(A) as the sum of the diagonal entries

The transpose A^T of a matrix

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement

Subspace topology: the traces of the open sets, its closed sets and its bases, the continuity of the inclusion, and the characteristic property of a map into a subspace

Embedded submanifolds and slice charts

A regular level set is an embedded submanifold

Slice-chart restrictions form a smooth atlas

The tangent space to a regular level set

Cʳ and smooth maps between smooth manifolds

Cᵏ maps and multi-index derivative notation in Euclidean space

If all partial derivatives exist on a neighbourhood and are continuous at a point, then the map is totally differentiable there with Jacobian derivative

Identity maps and composites of smooth maps are smooth

Critical points and critical values of a smooth function

The differential of a smooth real-valued function

The tangent space of a regular level set is the kernel

The tangent space of Euclidean space

Coordinate formula for the differential

Given: The data and facts above.

Goal: Establish the stated Gram properties, objective identity, feasible smooth structure and rank-one boundary case.

1.1 Entrywise multiplication gives $X_{ij}={\sum }_{a=1}^r{Y}_{ia}{Y}_{ja}=u_i\cdot u_j$, so $X$ is symmetric and $X_{ii}=1$. For any $c\in {\mathbb{R}}^n$, $c^{T}Xc={\sum }_{a=1}^r({\sum }_{i=1}^n{c}_i{Y}_{ia}{)}^2\ge 0$; hence $X$ is positive semidefinite. [given, F1, F2, F4, algebra]

1.2 Each row of $X=Y(Y^T)$ is a linear combination of the $r$ rows of $Y^T$. The row space of $X$ is therefore a subspace of the row space of $Y^T$. By equality of row and column ranks, the latter has dimension equal to the dimension of the column space of $Y^T$, a subspace of ${\mathbb{R}}^r$; its dimension is at most $r$. Thus $\mathrm{rank}X\le r$. [given, F1, F3, F4, algebra]

1.3 Each component $Q_i(Y)={\sum }_a{Y}_{ia}^2$ is smooth: its first coordinate partials are $2Y_{ia}$ in row $i$ and zero in other rows, its second partials are constants, and all partials of order at least three vanish. These functions are continuous. Its total derivative is consequently $DQ(Y)V=(2u_i\cdot v_i{)}_{i=1}^n$. The fibre over $(1,\dots ,1)$ is exactly $M_{n,r}$ and is nonempty, since every row can be $(1,0,\dots ,0)$. At a point of this fibre and for any $b\in {\mathbb{R}}^n$, the choice $v_i=(b_i\mathrm{/}2)u_i$ gives $DQ(Y)V=b$. By the Euclidean identifications and coordinate differential formula in [F9], $d{Q}_Y$ is consequently surjective at every point of this fibre. Thus this is a regular fibre. [given, F2, F6, F9, algebra, construct]

2.1 Expanding the trace and rearranging the finite sums yields $\mathrm{Tr}(Y^{T}BY)={\sum }_{a=1}^r{\sum }_{i,j=1}^n{Y}_{ia}{B}_{ij}{Y}_{ja}={\sum }_{i,j=1}^n{B}_{ij}(u_i\cdot u_j)$. This proves the objective identity and the stated Gram properties. [given, F1, F2, F4, step 1.1, step 1.2, algebra]

2.2 By the regular-fibre theorem, $M_{n,r}$ is an embedded smooth manifold of dimension $nr-n=n(r-1)$, with the relative Euclidean topology and the restricted slice-chart atlas. Apply [F9] to the smooth map $Q:{\mathbb{R}}^{nr}\to {\mathbb{R}}^n$ and its regular value $(1,\dots ,1)$ established in step 1.3: the intrinsic tangent space of this embedded fibre is identified with $\ker d{Q}_Y$. Under the canonical Euclidean tangent identifications, the coordinate formula in [F9] represents $d{Q}_Y$ by the already computed $DQ(Y)$, so this intrinsic tangent space is represented by exactly the matrices $V$ with $u_i\cdot v_i=0$ for every $i$. This also identifies it with the ambient constraint-kernel definition in [F7]. The squared Euclidean distance of the listed entries is ${\sum }_{i,a}(Z_{ia}-Y_{ia}{)}^2$, so the local-extremum definitions use neighbourhoods in precisely this relative topology. [F2, F5, F7, F9, step 1.3, algebra]

3.1 On the ambient matrix space, $\mathrm{Tr}(Z^{T}BZ)$ is a quadratic polynomial in the entries of $Z$, by the same expansion as step 2.1; its coordinate partials of order at least three vanish and its lower partials are continuous. It is therefore smooth. In a restricted slice chart of $M_{n,r}$ its coordinate expression is the composite of this ambient polynomial with the smooth inverse ambient chart and the linear slice inclusion $x\mapsto (x,0)$. This composite is smooth, so $F_B$ is smooth on $M_{n,r}$ and the critical-point definition in [F8] applies. [F1, F4, F6, F7, F8, step 2.1, step 2.2, algebra]

4.1 When $r=1$, the row equations are $u_i^2=1$, hence $u_i\in \{-1,1\}$. Distinct configurations have squared Euclidean distance at least $4$, so the relative ball of radius $1$ about any configuration contains only that configuration. Both local-extremum inequalities thus hold there. The tangent equations $u_i{v}_i=0$ force every $v_i=0$; the differential on this zero vector space is necessarily zero. Thus every rank-one configuration is critical as asserted. [given, F2, F5, F8, step 2.2, step 3.1, algebra] ∎

A landscape is the behavior of an objective on its feasible configurations, including its local extrema and critical points in the topology and smooth structure specified above. This definition alone makes no assertion about those points or about statistical recovery. Such assertions require a separately specified model and hypotheses; signed weights do not automatically satisfy inequalities proved for nonnegative weights.