PaperlayerView exact revision on arXiv

Source-linked AI summary

Fundamental Limits of Transferability and Equivariance in Algebraic Signal Models I: Finite Dimensions

Alejandro Parada-Mayorga

arXiv:2609.36106v1eess.SPcs.LG

TL;DR

The paper asks when processing can transfer between domains without retraining or redesign, and how much information survives. It develops a finite-dimensional algebraic theory using homomorphisms and filtered-spectrum coincidences, then relates those structures to sampling, compressed sensing, and equivariant learning. It concludes that these settings can be understood through shared coincidence-class structure, while noting that infinite-dimensional models require a separate treatment.

  • Problem

    The paper seeks a non-asymptotic structural account of when exact transfer between algebraic signal models is possible and how much information transfer preserves.

    Source: §I · p. 1, §VI · p. 12

  • Method

    The paper analyzes filter-commuting homomorphisms through filtered-spectrum coincidence classes and uses spectral transfer efficiency to assess information preservation.

    Source: A. When S and eS are Normal Operators · p. 6, §VI · p. 12

  • Results

    The paper relates transferability, sampling, compressed sensing, and equivariance to coincidence-class structure, with transfer quality and compressed-sensing measures controlled block by block.

    Source: §VI · p. 12

  • Takeaways & Limitations

    The paper presents transferability, equivariance, sampling, and compressed sensing as consequences of shared algebraic structure that can be designed and measured through filters.

    Source: §VI · p. 13

    The theory is restricted to finite-dimensional signal models; infinite-dimensional settings such as graphon and Lie-group models raise additional questions involving spectral type.

    Source: §VI · p. 12

Abstract

from arXiv · show

We study the fundamental limits of transferability in algebraic signal processing through homomorphisms between algebraic signal models. Homomorphisms are linear maps between the signal spaces of two models that commute with filtering, so filtering a signal and transferring it across domains can be done in either order. The existence of such maps is governed entirely by coincidences among the filtered eigenvalues of the two models' shift operators, but existence alone is insufficient: the space of homomorphisms always contains trivial elements that destroy all information. We introduce the spectral transfer efficiency $\eta(\theta)\in[0,1]$ to quantify information-preserving quality, prove that every homomorphism decomposes into unconstrained blocks over coincidence classes, derive the dimension of the homomorphism space, and characterize exactly when lossless transfer is achievable. Beyond normal shift operators, we quantify a departure-from-normality penalty and show how filter derivatives can repair spectral defectiveness. The theory yields concrete consequences in three settings: for sampling, eigenvalue interlacing converts transferability under subsampling into an explicit filter design constraint; for compressed sensing, $\eta(\theta)$ controls the restricted isometry constant and the coherence of the resulting measurements, and recovery decouples across coincidence classes; and for machine learning, spectral aliasing emerges as the controlled symmetry breaking that makes transfer between mismatched domains possible at all.

I. INTRODUCTION

The paper frames transferability and equivariance as algebraic questions about how filters act across signal models. It introduces algebraic signal processing as a common framework, then identifies filtered-spectrum coincidences and information preservation as central to transferability.

I. INTRODUCTION

  • A homomorphism transfers signals between models while commuting with filtering; when the models coincide, the same condition is equivariance.The framework treats discrete-time, graph, graphon, multigraph, and Lie group signal processing as instances of a shared algebraic construction.Source: §I · p. 1
  • Existing analyses are largely asymptotic or perturbative, leaving a need for a non-asymptotic account of exact transfer, available map degrees of freedom, and preserved information.The paper distinguishes the existence of homomorphisms from their informational usefulness because rank-deficient maps can satisfy the intertwining condition while destroying information.Source: §I · p. 1
  • In finite dimensions, nonzero transfer maps are governed by coincidences between the models’ filtered shift spectra, and each coincidence class supplies unconstrained map blocks.The paper also derives the homomorphism-space dimension and introduces spectral transfer efficiency to measure information preservation and characterize lossless transfer.Source: §I · pp. 1–2

II. ASP AND HOMOMORPHISMS BETWEEN SIGNAL MODELS

  • An algebraic signal model consists of an algebra of filters, a signal space, and a representation that realizes filters as operators on signals.The algebra holds abstract filters, the space holds signals, and the representation links them by turning filters into operators.Source: §II · p. 2
  • ASP separates the filter algebra from the representation on a particular domain, allowing the same algebraic framework to cover different concrete signal spaces and shift operators.The shift may represent a time delay, graph adjacency or Laplacian, or graphon integral operator.Source: §II · pp. 2–3

A. Homomorphisms Between Signal Models

A homomorphism between algebraic signal models is a linear transfer map that commutes with every filter. This condition links transferability to equivariance, while the dimension of the homomorphism space measures the available design freedom.

A. Homomorphisms Between Signal Models

  • A homomorphism transfers a filtered signal consistently because filtering before transfer gives the same result as transferring before filtering.The defining condition applies to every filter in the shared algebra and every source signal.Source: A. Homomorphisms Between Signal Models · p. 3
  • When source and target spaces and representations coincide, the homomorphism condition is precisely equivariance.The zero map also satisfies the condition, although it does not transfer information usefully.Source: A. Homomorphisms Between Signal Models · p. 3
  • The dimension of the homomorphism space measures the degrees of freedom for choosing a transfer map, and dimension zero means only the zero map exists.A larger dimension provides greater diversity and flexibility in choosing a map that satisfies the intertwining condition.Source: A. Homomorphisms Between Signal Models · p. 4
  • For an algebra generated by one element, a homomorphism also intertwines polynomial functions of the corresponding shift operators.The paper describes this as exchanging the shift operators in the polynomial operator between the two models.Source: A. Homomorphisms Between Signal Models · p. 4

III. HOMOMORPHISMS FOR TRANSFERABILITY IN FINITE ASMS

Transferability is a nonzero linear map between signal models that commutes with a chosen filter set; in finite single-generator models, its existence depends on coincidences between filtered eigenvalues. The paper then characterizes the maps’ block structure, information-preserving efficiency, and conditions for lossless transfer.

III. HOMOMORPHISMS FOR TRANSFERABILITY IN FINITE ASMS

  • Transferability requires a nonzero linear map that commutes with every filter in the chosen subset; without the nonzero condition, the zero map makes the definition vacuous.When the signal spaces and representations coincide, this condition includes equivariance.Source: §III · p. 4

A. Conditions and Limits of Transferability: A Primer

  • In finite models with a single generator, transferability is governed by coincidences p(λ_i) = p(eλ_j); greater map richness requires more such coincidences.Without any coincidence, the only intertwining map is zero; coincidences can arise from close spectra or filter flatness over misaligned spectral regions.Source: A. Conditions and Limits of… · pp. 4–5

A. When S and eS are Normal Operators

  • Every homomorphism acts only between matching filtered-spectral coincidence spaces and decomposes into independently chosen block maps on those spaces.It annihilates source eigenspaces whose filtered eigenvalues do not occur in the target spectrum.Source: A. When S and eS are Normal Operators · p. 5
  • Spectral transfer efficiency η(θ) detects information loss: it is zero when any block is non-injective and equals one when every block is a nonzero scaled isometry.Intermediate efficiency measures gain distortion within coincidence spaces; the measure also detects zero and rank-deficient homomorphisms.Source: A. When S and eS are Normal Operators · p. 6
  • For normal or diagonalizable shifts, the homomorphism-space dimension is the sum of source and target coincidence multiplicity products, and the maximum block rank is min(m_c, e m_c).The available degrees of freedom increase with the number of filtered-eigenvalue coincidences.Source: A. When S and eS are Normal Operators · p. 6
  • Lossless transfer is achievable exactly when each source coincidence space fits into its target counterpart; an injective global isometry requires this multiplicity condition at every coincidence value.If any source multiplicity exceeds its target multiplicity, every homomorphism loses information on that block.Source: A. When S and eS are Normal Operators · p. 7

B. Beyond Normality of S and eS

The normality assumption is relaxed to extend the analysis to non-normal shifts, with two scenarios considered.

B. Beyond Normality of S and eS

  • The analysis extends beyond normal shift operators by treating two scenarios separately.Normality was used to make spectral projections orthogonal and to make the filtered shift act as an exact scalar on each coincidence space.Source: B. Beyond Normality of S and eS · p. 7

1) Diagonalizable, non-normal shifts:

For diagonalizable non-normal shifts, the algebraic block decomposition survives using oblique spectral projections, but the ordinary metric decomposition can fail.

1) Diagonalizable, non-normal shifts:

  • For diagonalizable non-normal shifts, oblique spectral projections preserve the coincidence-space decomposition and the algebraic results; efficiency results hold using adapted inner products.These projections are polynomial in the filtered shifts, allowing the intertwining relation to pass to them.Source: 1) Diagonalizable, non-normal shifts · p. 7
  • Unlike the normal case, oblique coincidence spaces need not be orthogonal, so norm expansions include cross terms and the Pythagorean block identity need not hold.The same issue applies on the source and target sides; adapted inner products encode the discrepancy from the ambient metric.Source: 1) Diagonalizable, non-normal shifts · p. 7

2) Defective shifts and the role of p′:

For defective shifts, matching filtered eigenvalues is not enough: transfer blocks must also respect the shifts’ nilpotent structure. Filter derivatives can split Jordan blocks, increasing transfer freedom and sometimes restoring semisimplicity within a coincidence class.

2) Defective shifts and the role of p′:

  • A homomorphism block must intertwine the nilpotent parts, and full efficiency is generally impossible unless the source and target Jordan structures match exactly.A surplus of target dimension alone cannot overcome mismatched Jordan structure.Source: 2) Defective shifts and the role of p′ · pp. 7–8
  • If the first nonzero derivative of p at an eigenvalue is order r, each size-k Jordan block splits into r blocks whose sizes differ by at most one.When r = 1 the block passes intact; when r ≥ k it splits completely into size-1 blocks, making p(S) semisimple there.Source: 2) Defective shifts and the role of p′ · p. 8
  • For a size-2 source and target block, the intertwiner count is 2 rather than the semisimple count of 4, but complete splitting recovers all 4 degrees of freedom.The missing freedom comes from the nilpotent constraint; splitting both blocks removes it.Source: 2) Defective shifts and the role of p′ · p. 8
  • Once all blocks at a coincidence value split to size 1, the nilpotent constraint vanishes and the transfer block is free as in the semisimple case.Derivative flattening does not merge distinct eigenvalues or change coincidence classes, so the departure-from-normality penalty remains; aliasing can instead merge classes and reduce obliqueness.Source: 2) Defective shifts and the role of p′ · p. 8
  • Aliasing merges distinct eigenvalues into a coincidence class, whereas derivative flattening splits Jordan blocks within an already fixed class; both enlarge the admissible transfer space.Both mechanisms are controlled by the filter p.Source: 2) Defective shifts and the role of p′ · p. 8

V. APPLICATIONS

The applications interpret homomorphisms as sampling or measurement maps and turn spectral transfer conditions into design and recovery guarantees. Under node subsampling, interlacing specifies where filters must be flat; in compressed sensing, transfer richness bounds measurement quality and supports recovery by coincidence class.

A. Sampling, Pooling, and Dimensionality Reduction

  • When the target space is smaller, every transfer map annihilates at least N1 − N2 dimensions, but a scaled isometry remains possible on a band K if mc ≤ emc for every c in K.The unavoidable loss can be steered outside the band of interest.Source: A. Sampling, Pooling, and… · pp. 8–9
  • For node subsampling, interlacing places each retained eigenvalue in a bracket, so making p constant on each relevant bracket guarantees filtered coincidence regardless of the sampled nodes.The filter remains free to vary between brackets, localizing the loss of spectral discriminability to the regions needed for robust transfer.Source: A. Sampling, Pooling, and… · p. 9, Figure 4 · p. 9

B. Compressed Sensing: Recovery Guarantees for Measurements with Homomorphisms

  • For a band K with mc ≤ emc and injective blocks normalized to maximum singular value 1, the rescaled map’s RIC obeys δ_s(θ′) ≤ (1 − ηK(θ))/(1 + ηK(θ)) for s ≤ dim HK.The guarantee assumes normal shifts; block gains should be balanced because unequal gains can worsen global conditioning even when each block is rich.Source: B. Compressed Sensing: Recovery… · p. 9
  • Compressed sensing can operate in a strictly smaller target space while acting as a scaled isometry on the selected band; requiring that property across all classes instead forces N1 ≤ N2.The band-restricted design lets out-of-band content absorb the annihilation that compression makes unavoidable.Source: B. Compressed Sensing: Recovery… · p. 9

1) Coherence of Intertwining Measurements:

In the eigenbasis used to define sparsity, the measurement map’s columns inherit the coincidence-class structure. This makes coherence an intra-class quantity and allows sparse recovery to be analyzed class by class.

1) Coherence of Intertwining Measurements:

  • Columns from different coincidence classes are orthogonal, so the Gram matrix is block-diagonal and coherence is determined entirely within classes.This follows from each source direction mapping into its matching target subspace and the orthogonality of the target classes for normal shifts.Source: 1) Coherence of Intertwining… · p. 10
  • If mc > emc in any class, every homomorphism is rank-deficient there, forcing zero richness and strictly positive coherence when columns do not vanish.Rank-nullity drives both obstructions; they are two consequences of the same dimensional mismatch.Source: 1) Coherence of Intertwining… · p. 10
  • Zero coherence alone implies orthogonal columns, but richness reaches 1 only after equalizing their norms.Coherence normalizes columns and therefore does not penalize unequal gains, unlike η.Source: 1) Coherence of Intertwining… · p. 10
  • Sparse recovery through a homomorphism separates across coincidence classes, localizing recovery to smaller blocks with class-specific sparsity budgets.The classwise recovery requirement is strictly weaker than the cited global coherence condition.Source: 1) Coherence of Intertwining… · pp. 10–11

2) Recovery Guarantees Without Normality:

For diagonalizable but nonnormal shifts, the algebraic transfer structure remains, while oblique coincidence spaces degrade metric guarantees. The paper also distinguishes full shift-equivariance from filter-specific equivariance, showing how controlled spectral aliasing permits transfer between mismatched domains.

2) Recovery Guarantees Without Normality:

  • For diagonalizable shifts, the departure-from-normality penalty is κ(G)κ(eG) ≥ 1, with equality exactly when both shifts are normal.Even a homomorphism with η(θ) = 1 can transfer poorly in the ambient metric when coincidence spaces are far from orthogonal.Source: 2) Recovery Guarantees Without Normality · p. 11

C. Equivariance and Transferable Machine Learning

  • Full shift-equivariance requires raw eigenvalue matching, whereas p-equivariance permits matching only after filtering and thus allows aliasing.The two are different levels of symmetry constraint on transfer maps.Source: C. Equivariance and Transferable… · p. 11
  • With one source eigenvalue λ and one target eigenvalue µ ≠ λ but p(λ) = p(µ), full equivariance permits only the zero map while p-equivariance permits an isometry.The paper identifies aliasing as controlled symmetry breaking that makes transfer between spectrally mismatched domains possible.Source: C. Equivariance and Transferable… · p. 12
  • For neural networks, requiring transfer to commute with every filter in the algebra gives the rigid full-equivariant space, while requiring it only for the deployed filter bank gives a larger space when filters share level sets.The richness of the selected map measures per-layer information transfer at the linear stage.Source: C. Equivariance and Transferable… · p. 12

VI. DISCUSSION AND CONCLUSIONS

The paper treats transferability, sampling, compressed sensing, and equivariance as consequences of filtered-spectrum coincidences, with the filter as a shared design variable. Its conclusions are bounded by exact, worst-case analysis and a finite-dimensional setting, while identifying extensions beyond those boundaries.

VI. DISCUSSION AND CONCLUSIONS

  • Filtered-spectrum coincidences govern homomorphism existence, while spectral transfer efficiency adds a separate measure of how much information survives.This structure also makes the homomorphism-space dimension, restricted isometry constant, coherence, and equivariance achievability computable.Source: §VI · p. 12
  • Transferability, sampling, compressed sensing, and equivariance are different consequences of the same coincidence-class structure, with the filter as their shared design variable.The paper links these applications through which eigenvalues the filter identifies across domains.Source: §VI · pp. 12–13
  • For sampling, interlacing specifies where filters must be flat; for compressed sensing, efficiency controls recovery quantities; and spectral aliasing enables transfer between mismatched domains.The paper also reports that sparse recovery decouples across coincidence classes.Source: §VI · p. 12
  • The theory addresses exact and worst-case transfer, not domains that are merely close spectrally without exact shared filtered values.The minimum per-class efficiency supports uniform recovery guarantees but can let one small or inconsequential class dominate the reported quality.Source: §VI · pp. 12–13
  • The theory is limited to finite-dimensional models, and its sharpest Section IV results assume normal shift operators.The paper identifies infinite-dimensional spectral-type questions and multiple noncommuting generators as extensions; approximate homomorphisms could connect the exact theory to perturbative results.Source: §VI · p. 12

APPENDIX A PROOFS

The appendix establishes the homomorphism space's linear structure, reduces polynomial-filter transfer to an operator equation, and derives its dimension from spectral coincidences. It then proves that valid maps decompose into coincidence-class blocks and relates those intrinsic blocks to ambient-space operators.

A. Proof of Corollary 1

  • The homomorphisms commuting with a filter subset form a linear subspace of the linear maps between the two signal spaces.The proof uses closure under linear combinations and inclusion of the zero map.Source: A. Proof of Corollary 1 · p. 14

B. Proof of Corollary 2

  • For polynomial filters, intertwining the algebra generators implies the operator condition θp(S) = p(eS)θ.The proof obtains this by applying the representations to powers of the generator and extending by linearity.Source: B. Proof of Corollary 2 · p. 14

C. Proof of Theorem 1

  • The homomorphism-space dimension is the geometric multiplicity of zero for T, whose eigenvalues are filtered target-source eigenvalue differences.When no filtered eigenvalues coincide, T is invertible and the only homomorphism is the zero map.Source: C. Proof of Theorem 1 · p. 14

D. Proof of Lemma 1

  • Intertwining forces every off-diagonal block between distinct coincidence classes to vanish, leaving only maps within matching classes.The converse follows by checking the intertwining condition on each diagonal block.Source: D. Proof of Lemma 1 · p. 14

E. Block Maps and Their Ambient Extensions

  • Each intrinsic block is the restriction of θ from a source coincidence subspace to its matching target subspace, while its ambient extension is a zero-extension.Compressing the ambient operator to these subspaces loses no information because θ maps each source class into its corresponding target class.Source: E. Block Maps and Their Ambient… · p. 14

F. Proof of Proposition 1

The proofs establish blockwise counts and lossless-transfer conditions, extend these results to nonnormal shifts using adapted inner products, and characterize how polynomial filtering changes Jordan structure.

F. Proof of Proposition 1

  • dim Θp is the sum of mc emc over coincidence classes, because each unconstrained block maps Ec to eEc.The rank of each block can reach min(mc, emc).Source: F. Proof of Proposition 1 · p. 14

G. Proof of Proposition 2

  • A lossless isometric homomorphism exists when each source coincidence space embeds in its target counterpart; a source multiplicity excess prevents it.A missing target eigenvalue or mc > emc makes the corresponding block noninjective.Source: G. Proof of Proposition 2 · p. 15

H. Proof of Proposition 3

  • For nonnormal shifts, the block decomposition and dimension count remain unchanged, while gain-based isometry claims use adapted inner products.The adapted inner products make distinct coincidence spaces orthogonal; ambient-metric bounds are treated separately.Source: H. Proof of Proposition 3 · p. 15

I. Proof of Proposition 4

  • For Jordan blocks of sizes pi and qj, the intertwining-map space has dimension min(pi, qj), and lossless transfer at equal dimensions requires matching Jordan partitions.If the partitions differ, no scaled isometry exists and η(θ) < 1.Source: §I · p. 15

J. Proof of Lemma 2

  • If the first nonzero filter derivative at an eigenvalue has order r, a size-k Jordan block becomes r blocks sized ⌈k/r⌉ or ⌊k/r⌋.Order r = 1 leaves the block unchanged; r ≥ k makes the filtered operator semisimple on that generalized eigenspace.Source: J. Proof of Lemma 2 · p. 16

K. Proof of Proposition 5

On a normal-shift band, transfer efficiency yields a two-sided frame bound and an explicit restricted isometry constant, provided every active coincidence block can be embedded.

K. Proof of Proposition 5

  • The frame bound applies uniformly to every sparsity model on the band, not only a particular sparsity pattern.It holds for all x ∈ HK and every s ≤ dim HK.Source: K. Proof of Proposition 5 · p. 16
  • δ = (1 − ηK(θ))/(1 + ηK(θ)) gives the restricted isometry constant on the band for every sparsity level s ≤ dim HK.The bound follows from frame constants (ηK(θ), 1) under the stated gain normalization.Source: K. Proof of Proposition 5 · p. 16
  • The result is non-vacuous when mc ≤ emc for each active class, so every block can be chosen injective and ηK(θ) > 0.This condition permits each active θc to have positive minimum gain.Source: K. Proof of Proposition 5 · p. 17

L. Proof of Lemma 3

The proofs localize coherence to coincidence classes, relate block geometry to transfer efficiency, extend frame bounds to nonnormal shifts, and give eigenvalue-level conditions for lossless transfer.

L. Proof of Lemma 3

  • Measurement coherence is purely intra-class: columns mapped into different target coincidence spaces are orthogonal, so the maximum coherence occurs within one class.The coincidence spaces are mutually orthogonal when the target filtered shift is normal.Source: L. Proof of Lemma 3 · p. 17

M. Proof of Proposition 6

  • When mc ≤ emc in every class, a homomorphism can attain η(θ) = 1 and zero coherence by using scaled isometries on the blocks.The Welch-type lower bound also applies to coherence within a class.Source: M. Proof of Proposition 6 · p. 17

N. Proof of Proposition 7

  • For equal-norm block columns, ηc(θ) is the ratio of the extreme eigenvalues of the Gram operator; ηc(θ) = 1 exactly when the block is a scaled isometry.In that case the block’s off-diagonal inner products vanish.Source: N. Proof of Proposition 7 · p. 17

O. Proof of Proposition 8

  • For nonnormal shifts, frame bounds use condition numbers of the metric operators; when both shifts are normal, those condition numbers are 1 and the bound reduces to the normal case.The adapted inner products make coincidence spaces orthogonal for the nonnormal proof.Source: O. Proof of Proposition 8 · p. 17

P. Proof of Proposition 9

  • Lossless eigenvalue-level transfer requires every source eigenvalue to occur in the target with no greater multiplicity, and each class must use one common scale.Different scales within a coincidence class lower its efficiency; a missing or over-multiplicity eigenvalue forces global efficiency to zero.Source: P. Proof of Proposition 9 · pp. 17–18
Loading 2609.36106v1…