Unrolled reconstruction and finite-iteration limits

Let $n,m\ge 1$, $X={\mathbb{R}}^n$, and let $\mathrm{\Omega }$ be a Borel subset of ${\mathbb{R}}^{m\times n}\times {\mathbb{R}}^m$ with its relative Borel sigma-algebra. Equip $\mathrm{\Omega }\times X$ with the finite product sigma-algebra $\mathcal{B}(\mathrm{\Omega })\otimes \mathcal{B}(X)$. Fix an integer $N\ge 0$, real parameters ${\tau }_0,\dots ,{\tau }_{N-1}$, a Borel initialization $I:\mathrm{\Omega }\to X$, Borel sets $D_k\subseteq \mathrm{\Omega }\times X$, and Borel maps $B_k:D_k\to X$ for $0\le k<N$, where each $D_k$ carries its relative product sigma-algebra. For $p=(A,y)\in \mathrm{\Omega }$ and $x\in X$, define $c(p,x)=A^{\mathsf{T}}(y-Ax)$. Set $E_0=\mathrm{\Omega }$ and $x_0=I$; recursively, for $0\le k<N$, set

$E_{k+1}:=\{p\in E_k:(p,x_k(p)+{\tau }_{k}c(p,x_k(p)))\in D_k\},x_{k+1}(p):=B_k(p,x_k(p)+{\tau }_{k}c(p,x_k(p)))(p\in E_{k+1})\mathrm{.}$

Then every $E_k$ is a Borel subset of $\mathrm{\Omega }$ and every $x_k:E_k\to X$ is Borel. In particular, $E_N$ is exactly the set of inputs where all $N$ updates are defined, and the finite output map $x_N:E_N\to X$ is Borel.

Measurable spaces and relative measurable subsets.

Measurable maps are characterized by measurable preimages.

Finite product sigma-algebras are generated by measurable rectangles.

Continuous maps have Borel preimages of Borel sets.

Composition preserves measurability.

Let $n,m\ge 1$ be integers, $X={\mathbb{R}}^n$, and $Y={\mathbb{R}}^m$ with their standard Euclidean inner products and Borel sigma-algebras. Borel sets are members of the sigma-algebra generated by open sets, and a map is Borel if preimages of Borel sets are Borel. An instance is a pair $(A,y)$ in a declared Borel set $\mathcal{D}\subseteq {\mathbb{R}}^{m\times n}\times Y$, where $A$ is the measurement matrix, $y$ is the observed data, and $A^{\mathsf{T}}$ is the transpose matrix. For fixed $A$, the forward map is $F_A:X\to Y$, $F_A(x)=Ax$, and the reconstruction target is the signal $x$ itself. For $x\in X$, define the data-consistency correction by $c(A,y,x):=A^{\mathsf{T}}(y-Ax)$.

For an integer depth $N\ge 1$, an unrolled regularization architecture consists of a Borel initialization map $I_{\theta }:\mathcal{D}\to X$, parameters $\theta =({\theta }_0,\dots ,{\theta }_{N-1})$ and real step parameters ${\tau }_0,\dots ,{\tau }_{N-1}$ held fixed at deployment, and Borel update maps $B_{{\theta }_k}:D_k\to X$ with $D_k\subseteq \mathcal{D}\times X$ Borel. Set $x_0=I_{\theta }(A,y)$ and, for $k=0,\dots ,N-1$, set

$x_{k+1}=B_{{\theta }_k}((A,y),x_k+{\tau }_{k}c(A,y,x_k))\mathrm{.}$

For fixed parameters and depth, let ${\mathcal{D}}_{\theta ,N}$ be the Borel subset of $\mathcal{D}$ for which the initialization and all $N$ recursive evaluations are defined. For $(A,y)\in {\mathcal{D}}_{\theta ,N}$, write $U_{{\theta }_k}^{A,y}(x):=B_{{\theta }_k}((A,y),x+{\tau }_{k}c(A,y,x))$. The deployed map is

${\mathrm{\Phi }}_{\theta ,N}(A,y)=(U_{{\theta }_{N-1}}^{A,y}\circ \cdots \circ U_{{\theta }_0}^{A,y})(I_{\theta }(A,y))\mathrm{.}$

Admissibility requires this finite map to be Borel; it is a point reconstruction rule from the input pair $(A,y)$ to the signal target in $X$, not a probability-distribution-valued rule. The parameters may have been selected by any training procedure, and the architecture supplies no training-law specification or convergence, data-residual, or test-risk guarantee.

An exact proximal block is permitted when, for each fixed $(A,y)$, $B_{{\theta }_k}((A,y),v)={\mathrm{prox}}_{{\alpha }_{k}g}(v)$ for some ${\alpha }_k>0$, where $g=g_{{\theta }_k,(A,y)}:{\mathbb{R}}^n\to (-\mathrm{\infty },+\mathrm{\infty }]$ has nonempty effective domain $\{u:g(u)<+\mathrm{\infty }\}$, satisfies $g((1-\lambda )u+\lambda v)\le (1-\lambda )g(u)+\lambda g(v)$ for $u,v\in {\mathbb{R}}^n$ and $0\le \lambda \le 1$, and has closed epigraph $\{(u,s):g(u)\le s\}$. Here ${\mathrm{prox}}_{\alpha g}(v)$ denotes the unique global minimizer $u\in {\mathbb{R}}^n$ of $g(u)+\mathrm{\parallel }u-v{\mathrm{\parallel }}_2^2\mathrm{/}(2\alpha )$. The proximal-map existence theorem supplies uniqueness under precisely these hypotheses. A general learned block is not assumed to be a proximal map or to minimize any objective.

For differentiation, fix an admissible data pair $(A,y)$ and regard the desired trainable parameter coordinates, including any step parameters to be differentiated, as a finite-dimensional input vector $\eta$ in an open parameter set; hold the other values fixed. At the differentiation point ${\eta }_0$, require an open neighborhood $V$ of ${\eta }_0$ on which the actual initialization and all $N$ deployed updates are defined for this fixed $(A,y)$. Require the graph below to evaluate those same maps for every $\eta \in V$; a smooth extension beyond a declared Borel domain alone does not meet this requirement. Without such a neighborhood, no derivative of the deployed map is asserted. Construct a finite straight-line graph with input $\eta$, initialization node $x_0=I_{\theta }(A,y)$, and, for each $k=0,\dots ,N-1$, distinct nodes

$v_k=x_k+{\tau }_k{A}^{\mathsf{T}}(y-A{x}_k),x_{k+1}=B_{{\theta }_k}((A,y),v_k)\mathrm{.}$

Its output nodes are the coordinates of $x_N$. Thus each stage uses its own map $B_{{\theta }_k}$ and step parameter ${\tau }_k$; no common update map or shared layer parameter is required. Represent each initialization and update by its constituent primitive nodes or by a supplied complete deterministic $C^1$ primitive with its derivative rule; an opaque call without that map and rule is not an admissible graph primitive. Require every graph primitive to be continuously differentiable on an open neighborhood of its visited inputs. For a piecewise-$C^1$ primitive, each visited input must lie strictly inside a declared branch region, with that branch label fixed on an open neighborhood of the input; at a branch boundary or ambiguous branch selection the automatic-differentiation procedure returns no derivative. Apply forward-mode automatic differentiation to each scalar output-coordinate graph in the desired parameter direction. The forward-mode correctness theorem then identifies the returned tangent with the directional derivative of that finite output; coordinate directions give the Jacobian. When all stages instead repeat one $C^1$ map $G(z,\theta )$ with a common parameter, the finite fixed-point-iteration procedure is the corresponding specialization. This differentiates only the deployed finite map and adds no assertion about an infinite iteration.

For $N\ge 3$, the diagram compresses the intervening states and updates into a single arrow; when $N=3$, that arrow is the single update $U_{{\theta }_1}^{A,y}$. For $N=1$ and $N=2$, the recurrence above gives the corresponding one- and two-update chains. At one fixed admissible $(A,y)$, every arrow denotes finite function application, not a limit.

Monga, Li, and Eldar, full algorithm-unrolling treatment

Gregor and LeCun, fixed-depth LISTA construction

Clason, full lecture notes on Landweber regularization

Point estimators and finite unrolled learned-update interface.

Finite graph and primitive conventions.

Borel measurable spaces for the data and signal domains.

Borel maps are characterized by Borel preimages.

Finite product Borel structure on layer inputs.

Automatic differentiation of a finite iteration.

Forward-mode differentiation of a finite computational graph.

Correctness of forward mode on a fixed strict branch.

The proper closed convex proximal-map interface.

The proper closed convex epigraph convention used by the proximal branch.

Existence and uniqueness of the proximal minimizer under those hypotheses.

The finite recursive domain and output are Borel.

Let $N\ge 1$ and let ${\mathrm{\Phi }}_{\theta ,N}$ be the point-valued map obtained by an initialization followed by $N$ defined, fixed-parameter update maps on an admissible input $(A,y)$. This finite definition does not imply that the iterates of an underlying infinite recurrence converge: even the repeated scalar update $T(x)=2x$ is defined at every finite depth from $x_0=1$, while $T^k(x_0)=2^k$ diverges.

For the risk comparison, fix a nonempty Borel input space $E\subseteq {\mathcal{D}}_{\theta ,N}$ for every parameter $\theta$ under consideration, and restrict each deployed map to $E$. For squared reconstruction loss $\mathrm{\ell }(t,a)=\mathrm{\parallel }a-t{\mathrm{\parallel }}_2^2$ on the signal space, let $\mathcal{S}=\{(A_i,y_i,x_i^{†}){\}}_{i=1}^s$ be a nonempty finite training set with $(A_i,y_i)\in E$ and $x_i^{†}\in X$, $s\ge 1$, and let $P_{\mathcal{S}}=s^{-1}{\sum }_{i=1}^s{\delta }_{((A_i,y_i),x_i^{†})}$ be its empirical joint law. The training-law risk is $L_{\mathcal{S}}(\theta )=R_{P_{\mathcal{S}}}({\mathrm{\Phi }}_{\theta ,N})$, where $R_P(g)$ is the expected loss of the Borel point rule $g$ under the joint input-target law $P$. At a shifted input $(A,y)\in E$, the forward residual is $\mathrm{\parallel }A{\mathrm{\Phi }}_{\theta ,N}(A,y)-y{\mathrm{\parallel }}_2$, and for a test probability law $Q$ on $E\times X$ the test risk is $R_Q(\theta )=R_Q({\mathrm{\Phi }}_{\theta ,N})$ when this expectation is defined. No bound on either quantity follows from a bound on $L_{\mathcal{S}}$ alone: for every $M>0$ there is a one-sample scalar training law with zero training-law risk and a shifted scalar operator with forward residual and squared test risk both greater than $M$.

For a recurrence $z_{k+1}=G(z_k,\theta )$, a fixed point at parameter $\theta$ is a state $z_{\ast }(\theta )$ satisfying $G(z_{\ast }(\theta ),\theta )=z_{\ast }(\theta )$. If the initialization and update maps are continuously differentiable in their state and trainable-parameter variables on open neighborhoods of their visited inputs, automatic differentiation through the deployed graph computes the derivative of that finite map. For a piecewise-$C^1$ primitive, assume each visited input lies strictly inside one declared branch, with its branch label fixed on an open neighborhood; at a branch boundary or ambiguous branch selection no derivative is asserted by the automatic-differentiation procedure. The derivative is that of the finite map and is not replaced by the derivative of a limiting fixed point. In particular, for $G(z,\theta )=qz+(1-q)\theta$ with $0<q<1$, $z_0(\theta )=0$, and ${\theta }_0=0$, each finite iterate has zero fixed-point residual while its parameter derivative differs from the exact fixed-point derivative.

Monga, Li, and Eldar, full unrolling survey and conditional LISTA convergence results

Gregor and LeCun, fixed-depth LISTA and its training loss

Clason, exact Landweber convergence and early stopping hypotheses

Zheng et al., dataset-scoped out-of-distribution experiments

Daras et al., finite-computation and method-specific asymptotic limits

The finite unrolled map and layer convention.

Borel point-estimator and finite learned-update interface.

Expected loss under joint train and test laws.

The finite-iteration automatic-differentiation procedure.