Low-Rank Separable Functions And Neural Approximation

Why Separable Structure Can Reduce Approximation Cost

A general function of many variables may be difficult to approximate because its behavior can vary jointly across all input coordinates. But some functions have a more organized form: they are sums of products, and each product factor depends on only a small group of coordinates. Neural networks can exploit this structure by approximating the factors separately and then combining them. The resulting bound depends on the dimensions and smoothness of the factors, not necessarily on the full input dimension.

The gain is conditional, not automatic. A function must admit a useful low-rank representation relative to a specified partition. Even then, the bound below is a constructive upper bound; it does not claim that the representation has minimal rank or that no smaller network exists.

Separable Rank Relative to a Partition

Definition: Let the input domain be $[0,1]^d$, and fix a partition $I_1,\ldots,I_m$ of $\{1,\ldots,d\}$ into nonempty, disjoint coordinate sets. Write $x_{I_j}$ for the subvector whose coordinates have indices in $I_j$. A function $f$ has a separable representation of rank at most $R$ relative to this partition if $$ f(x)=\sum_{r=1}^{R} a_r\prod_{j=1}^{m} g_{rj}(x_{I_j}), $$ where $a_r$ are real coefficients and each factor $g_{rj}$ depends only on the coordinates in $I_j$. The least such $R$, when it exists, is the separable rank relative to the specified partition.

The partition is part of the definition: changing the coordinate blocks can change the rank and the complexity of the factors. A factor on a block of $q_j=|I_j|$ coordinates is a $q_j$-dimensional function, even if the original input has $d$ coordinates. This is the source of the potential approximation advantage.

Worked Example: A Rank-One Function With Three Fixed Blocks

On $[0,1]^4$, take the partition $I_1=\{1,2\}$, $I_2=\{3\}$, and $I_3=\{4\}$, and define $$ f(x)=(x_1^2+x_2)x_3x_4. $$

This is a rank-one representation with $m=3$ factors: $$ g_{11}(x_{I_1})=x_1^2+x_2,\qquad g_{12}(x_{I_2})=x_3,\qquad g_{13}(x_{I_3})=x_4. $$ The coordinate blocks are disjoint and together contain all four coordinates. In particular, the last two factors use the singleton blocks $\{3\}$ and $\{4\}$; neither factor uses the block $\{3,4\}$.

For example, at $x=(1/2,1/4,1/3,3/4)$, the first factor is $1/4+1/4=1/2$, and the product is $$ f(x)=\frac12\cdot\frac13\cdot\frac34=\frac18. $$ The factor $x_1^2+x_2$ is smooth on a two-dimensional block, while the remaining factors are one-dimensional linear functions. The representation makes these differing factor dimensions explicit.

From Factor Approximation to Function Approximation

We measure approximation error in the uniform norm, $\|h\|_\infty=\sup_{x\in[0,1]^d}|h(x)|$. The key calculation is that errors in the factors accumulate in a controlled way when the factors are bounded. We will also use the ReLU multiplication approximation: for fixed $M\geq 1$, a network can approximate multiplication on a bounded domain to error $\eta$, with parameter count at most $C_M(1+\log(1/\eta))$ for $0<\eta<1/2$. This is the multiplication construction from the earlier material on ReLU networks for multiplication. For a fixed number $m$ of inputs, composing such modules gives a network that approximates their product uniformly on $[-M,M]^m$, with parameter count at most $C_{m,M}(1+\log(1/\eta))$, after adjusting the constant and internal error tolerances.

Theorem: Suppose $$ f(x)=\sum_{r=1}^{R}a_r\prod_{j=1}^{m}g_{rj}(x_{I_j}) $$ on $[0,1]^d$, where $|a_r|\leq A$ and $\|g_{rj}\|_\infty\leq B$ for all $r,j$, with $A>0$, $B\geq 0$. For $0<\varepsilon$ sufficiently small, suppose that for every factor there is a ReLU network $\widetilde g_{rj}$ satisfying $\|g_{rj}-\widetilde g_{rj}\|_\infty\leq\delta$, where $$ \delta=\frac{\varepsilon}{2RA\,m(B+1)^{m-1}}\leq 1. $$ Then there is a ReLU network $F$ with $\|f-F\|_\infty\leq\varepsilon$. It can be built with parameter count at most the sum of the parameter counts of the $Rm$ factor networks, plus $R C_{m,B+1}(1+\log(2RA/\varepsilon))$, and an affine output layer. The constant in the multiplication-module bound depends on $m$ and $B$, not on $d$, $R$, or $\varepsilon$.

Proof. Since $\delta\leq1$, every approximate factor satisfies $|\widetilde g_{rj}|\leq B+1$. For a fixed rank term $r$, subtract the product of the true factors from the product of the approximate factors by replacing one factor at a time. This gives the exact telescoping identity $$ \prod_{j=1}^{m}\widetilde g_{rj}-\prod_{j=1}^{m}g_{rj} =\sum_{k=1}^{m} \left(\prod_{j<k}\widetilde g_{rj}\right) (\widetilde g_{rk}-g_{rk}) \left(\prod_{j>k}g_{rj}\right). $$ In the $k$th summand, each of the $m-1$ factors other than the difference is bounded in absolute value by $B+1$, and the difference is bounded by $\delta$. Therefore $$ \left|\prod_{j=1}^{m}\widetilde g_{rj}-\prod_{j=1}^{m}g_{rj}\right| \leq m(B+1)^{m-1}\delta. $$ After multiplication by $|a_r|\leq A$ and summation over $R$ terms, the total factor-approximation error is at most $RA m(B+1)^{m-1}\delta=\varepsilon/2$.

For each $r$, use the fixed-arity multiplication network on the $m$ approximate factors, whose inputs lie in $[-(B+1),B+1]^m$, with uniform error $\eta=\varepsilon/(2RA)$. For sufficiently small $\varepsilon$, this is within the multiplication lemma's stated range. The weighted sum of the $R$ computed products contributes at most $RA\eta=\varepsilon/2$ additional error. The triangle inequality now gives $\|f-F\|_\infty\leq\varepsilon$. The factor networks are used once each, there is one multiplication module per rank term, and their outputs are combined by an affine layer. This gives the claimed parameter count. $\square$

How Smoothness and Factor Dimension Enter the Size

The theorem separates the structural calculation from the approximation rate for each factor. To turn it into a size bound, use a smooth-function approximation result for each factor: for fixed input dimension $q$, smoothness $s>0$, and a bounded Hölder class on $[0,1]^q$, ReLU networks achieve uniform error $\delta$ with parameter count at most $$ C\,\delta^{-q/s}\log(1/\delta) $$ for sufficiently small $\delta$. Here the constant may depend on the dimension, smoothness, and Hölder-norm bound. This is the factor-level rate from the earlier material on ReLU approximation rates for Hölder functions; it is not a claim that every factor has the same dimension or smoothness.

For factor $g_{rj}$, write $q_j=|I_j|$ and let its smoothness be $s_{rj}$. Applying that rate with the $\delta$ in the theorem and summing over factors yields the constructive bound $$ C_{m,B,A}\sum_{r=1}^{R}\sum_{j=1}^{m} \delta^{-q_j/s_{rj}}\log(1/\delta) \;+\; R C_{m,B+1}\bigl(1+\log(2RA/\varepsilon)\bigr), \qquad \delta=\frac{\varepsilon}{2RA\,m(B+1)^{m-1}}. $$ Constants may differ across factors if their smoothness or norm bounds differ. With a common block dimension $q$, common smoothness $s$, and fixed $m,A,B$, the leading factor-network contribution scales as $R(R/\varepsilon)^{q/s}$, up to logarithmic factors and constants. Thus increasing rank costs more terms, while smoother factors or smaller blocks reduce the factor approximation cost. This is an upper bound for this construction, not a universal lower bound or a guarantee of improvement for every target.

Worked Example: A Three-Term Representation and Its Error Budget

On $[0,1]^3$, use blocks $I_1=\{1,2\}$ and $I_2=\{3\}$, and consider $$ f(x)=(x_1+x_2)x_3+(x_1-x_2)(1-x_3)+x_1x_2. $$ This has a representation of rank at most $3$: the three pairs of factors are $(x_1+x_2,x_3)$, $(x_1-x_2,1-x_3)$, and $(x_1x_2,1)$, all with coefficient $1$. We do not assert that $3$ is the minimal rank.

At $x=(0.2,0.6,0.25)$, the three terms are $0.8(0.25)=0.20$, $(-0.4)(0.75)=-0.30$, and $0.2(0.6)=0.12$. Hence $f(x)=0.20-0.30+0.12=0.02$. Every factor is bounded by $B=2$, so take $A=1$, $R=3$, $m=2$. For target error $\varepsilon=0.03$, the theorem sets $$ \delta=\frac{0.03}{2\cdot3\cdot1\cdot2\cdot(2+1)} =\frac{0.03}{36} =\frac{1}{1200}, \qquad \eta=\frac{0.03}{2\cdot3} =0.005. $$ The total contribution from factor errors is at most $3\cdot1\cdot2\cdot3\cdot(1/1200)=0.015$. The three multiplication modules contribute at most $3\cdot1\cdot0.005=0.015$. Their sum is $0.03$, as required.

If the two-dimensional factors have smoothness $s$, their individual network sizes scale, up to constants and logarithms, as $\delta^{-2/s}$; the one-dimensional factors scale as $\delta^{-1/s}$. The smaller one-dimensional factors therefore require less approximation capacity at a common smoothness and accuracy.

Worked Example: A Low-Dimensional Smoothness Rate

Suppose a function on $[0,1]^5$ is represented with $R=4$ terms and $m=2$ blocks of dimensions $q_1=2$ and $q_2=3$. Assume $A=B=1$, and suppose all factors belong to bounded Hölder classes of smoothness $s=1$. For $\varepsilon=0.1$, the theorem gives $B+1=2$ and $$ \delta=\frac{0.1}{2\cdot4\cdot1\cdot2\cdot2} =\frac{0.1}{32} =0.003125=\frac{1}{320}. $$

For each two-dimensional factor, the smoothness rate has a leading power $\delta^{-2}=320^2=102{,}400$, up to a logarithm and its class-dependent constant. For each three-dimensional factor the leading power is $\delta^{-3}=320^3=32{,}768{,}000$, again up to a logarithm and a constant. There are four factors of each dimension. The cubic-block factors dominate this bound, even though the full input dimension is five.

This example also shows why “low rank” alone does not determine size: the dimensions and smoothness of the factors matter. A representation with four terms can still be expensive if its factors are high-dimensional or rough.

Interpreting the Bound and Avoiding a Common Error

The benefit of separability is most visible when the partition produces substantially smaller blocks than the full input dimension. A generic approximation bound for a $d$-dimensional smooth function has a power involving $d/s$; a separable construction instead pays factorwise powers involving $q_j/s_{rj}$, along with the number of terms and the error allocation across them. The construction is particularly useful when the rank is moderate and each factor is substantially smoother or lower-dimensional than the unrestricted target.

Rank is relative to a partition. A statement that a function has rank $R$ is incomplete unless the coordinate blocks are specified.
Rank is not a size bound by itself. Factor dimensions, smoothness, bounds, and desired accuracy all enter the network budget.
The bound is sufficient, not necessary. The theorem constructs one network; algebraic identities or special forms may allow a smaller one.

A common mistake is to approximate each factor to error $\varepsilon$ and then conclude that the sum of products also has error $\varepsilon$. That reasoning ignores accumulation across the $m$ factors and the $R$ rank terms. The correction is to telescope each product error, bound each of its $m$ summands, and allocate a smaller factor tolerance—here proportional to $\varepsilon/R$—before summing. The partition must also remain fixed throughout: factors depending on $\{3\}$ and $\{4\}$ cannot be described using a single block $\{3,4\}$ while retaining a three-block representation.

Key takeaway: For a low-rank separable target, approximate the factors on their own coordinate blocks and implement each product with a multiplication network. The resulting accuracy and size depend jointly on rank, block dimensions, factor smoothness, and the chosen error allocation.

Check Your Understanding

Use the definitions and error calculation above to answer these questions.

For a fixed partition, what must be true of the coordinate sets $I_1,\ldots,I_m$ in a separable representation?
If each factor is approximated within $\delta$, why can the error in one product involve $m$ contributions rather than just one?
For fixed rank and smoothness, how does changing a factor block from dimension $q=2$ to $q=4$ affect the power of the inverse accuracy in the stated Hölder rate?
In the three-term example, verify the function value at $x=(0.2,0.6,0.25)$ by calculating each term separately.
Why does a rank-based network-size upper bound not establish that the rank is minimal or that the constructed network is optimal?