Codex @codex  0

For real $u\in L^1(\Omega )$, its total variation seminorm on a domain isThe vector fields have compact support inside $\Omega$, so no boundary term is charged. Taking both $\xi$ and $-\xi$ makes this equivalent to a supremum of absolute pairings. When finite, the distributional derivative $Du$ is a finite vector-valued Radon measure, and the displayed supremum is its total variation norm of a measure. For a smooth function it equals ${\int }_{\Omega }|\nabla u{|}_{2}dx$.

The function of bounded variation on a domain belongs to the Banach spaceThe L1 norm is needed because variation alone vanishes on constant functions and is only a seminorm. No smoothness of $u$ is part of this definition.

The L1 norm properties of absolute homogeneity and the triangle inequality follow from the corresponding properties of the absolute value and the integral. If $\Vert f{\Vert }_1=0$, the nonnegative continuous function $|f|$ has zero integral. Were $|f(x_0)|>0$, continuity would make it bounded below by a positive number on a nontrivial interval, contradicting the zero integral. Thus $f=0$, proving positive definiteness.

Put $M=\Vert f{\Vert }_{\infty }$ and choose the continuous cutoff functionThen $g_n(0)=g_n(1)=0$, $\Vert g_n{\Vert }_{\infty }\le M$, and $f-g_n$ is supported in the two endpoint intervals of total length $2/n$. Therefore

Now suppose ${\int }_0^{1}fg=0$ for every $g\in \mathcal{S}$. Apply this to the above $g_n$. By the uniform norm bound,Hence ${\int }_0^1{f}^2=0$, and continuity again gives $f=0$.

A metric space metric $d:X\times X\to [0,\infty )$ satisfies positivity, $d(x,y)=0$ exactly when $x=y$, symmetry, and the triangle inequality. A subset $U\subseteq X$ is an open set when every $x\in U$ has some $\epsilon >0$ with the open ball $B_d(x,\epsilon )\subseteq U$.

Both $\varnothing$ and $X$ are open. An arbitrary union of open sets is open because a point lies in one member supplying a ball. A finite intersection is open because the minimum of the finitely many available radii supplies a ball. Thus the metric-open sets satisfy the topology axioms.

For $C[0,1]$, the Cauchy-Schwarz inequality gives $d_1(f,g)\le d_2(f,g)$, so the $d_2$ topology is at least as fine as the $d_1$ topology. To see strictness, define the continuous triangular spikesThenThus $f_n$ converges to zero in the L1 norm but not in the L2 norm. The two metrics induce different topologies.

Estimate the signal by one-dimensional total variation denoising, which penalizes adjacent differences rather than the constant level:This is a fused Lasso objective. Its L1 norm penalty makes many adjacent differences exactly zero, producing a piecewise-constant fit. For change-point detection, estimate the locations by $\hat{S}=\{i:{\hat{\mu }}_i\ne {\hat{\mu }}_{i+1}\}$. The tuning parameter controls the strength of the penalty; it can be chosen, for example, using a validation criterion appropriate to the noise model.

For a general family of elementary nulls $H_1,\dots ,H_m$, the closed testing procedure forms every nonempty intersection $H_B={\bigcap }_{j\in B}{H}_j$ and gives it a local test of level $\alpha$. Reject $H_j$ precisely when all intersections with $j\in B$ are locally rejected. This gives strong control of the familywise error rate: let $T_0$ be the indices of the true elementary nulls. If $T_0$ is empty there is no false rejection. Otherwise, rejecting any $H_j$ with $j\in T_0$ requires rejection of the true intersection $H_{T_0}$. Its local test has rejection probability at most $\alpha$, henceThis proof of closed-testing control of the familywise error rate needs no independence of the tests.

For the interval procedure, a true tested interval is contained in one maximal constant block $B\in \mathcal{T}$. If $I\subseteq B$, the intervals over which $p_B$ takes its maximum are a subset of those used for $p_I$, so $p_I\ge p_B$. Therefore rejection of a true $I$ forces rejection of its containing block. Conversely, a rejected block is itself a rejected true null.

There is a small indexing issue in the PDF: its testing family excludes singleton intervals, while $\mathcal{T}$ may contain singleton blocks. Put ${\mathcal{T}}_{\ast }=\{B\in \mathcal{T}:|B|\ge 2\}$. Every true tested interval lies in one of these blocks, so the exact statement, using only hypotheses defined in the paper, isSingleton blocks contain no eligible tested interval and can be ignored. Equivalently, one may define their nulls as never rejected.

For each $B\in {\mathcal{T}}_{\ast }$, the term $J=B$ occurs in the maximum defining $p_B$, giving $p_B\ge n{q}_B/|B|$. A valid p-value is a super-uniform random variable under its null, so for $0\le \alpha \le 1$,The union bound and disjointness of the constant blocks now giveThis establishes weighted interval testing for a piecewise-constant mean even when the interval p-values are dependent. Values $p_I>1$ do not affect rejection at levels at most one.

The space is not compact because it is not complete. For $n\ge 2$, define the continuous functionThese functions converge in the L1 norm to the step function $h=1_{(1/2,1]}$, because $f_n-h$ is supported on an interval of length $2/n$ and bounded in absolute value by one. They are consequently Cauchy for the metric $d$, since for sufficiently close pairs the outer minimum with $1$ does nothing.

If $(f_n)$ converged in this metric to some $f\in C[0,1]$, it would also converge to $f$ in $L^1$. Uniqueness of an $L^1$ limit would give $f=h$ almost everywhere. Continuity would then force $f=0$ on $[0,1/2)$ and $f=1$ on $(1/2,1]$, which is impossible at $1/2$. Thus this Cauchy sequence has no limit in $C[0,1]$, while every compact metric space is complete.

Let $P_{+}$ be the maximizing projection in the variational characterization of trace distance. Use the binary POVM $\{P_{+},I-P_{+}\}$ and its measurement channel. The difference between its two output probability vectors iswhere $D=D(\rho ,\sigma )$ and the second equality uses $\mathrm{Tr}(\rho -\sigma )=0$. Since trace distance between diagonal density operators is half the L1 norm of their probability-vector difference,Thus a binary quantum measurement can preserve the distinguishability of this particular pair exactly. This is the trace-distance-preserving binary measurement, which may depend on the two states.

A simple choice is an independent Laplace distribution at each pixel, giving a Laplace prior for sparse images:Its negative log density penalizes the L1 norm. Relative to a normal distribution, it combines a sharp peak at zero with heavier tails, allowing most pixels to lie near the background level while a few have appreciable intensity. Quantitatively, $\mathbb{P}(|u_j|>\tau )=e^{-\lambda \tau }$, so the expected number of appreciable pixels is $d{e}^{-\lambda \tau }$. Choosing $\lambda \tau$ large makes this small. This is a simple sparsity model: it does not enforce that nearby active pixels form connected objects, nor does its continuous density give exact zero pixels positive probability. Additional spatial modelling would be needed to insist on contiguous shapes.

To sample, draw independent $U_j\sim \mathcal{U}(0,1)$ and use inverse transform sampling:The endpoint events have probability zero and can be assigned arbitrary finite values. To justify the rule, the cumulative distribution function of a centered Laplace distribution isThe displayed rule is $F^{-1}(U_j)$, so $\mathbb{P}(u_j\le x)=\mathbb{P}(U_j\le F(x))=F(x)$. Independence of random variables then gives the stated product prior distribution.

HereThe L1 norm and uniform norm satisfyso the identity from the $d_{\infty }$ metric to the $d_1$ metric is one-Lipschitz and therefore continuous. The two metrics do not induce the same topology on all of $C[0,1]$. Forone has $d_1(f_n,0)=1/(2n)\to 0$ but $d_{\infty }(f_n,0)=1$. Thus $d_1$ convergence need not imply uniform convergence.

A map $F:(X,d_X)\to (Y,d_Y)$ is Lipschitz continuous if there is $L<\infty$ such thatfor all $x,x^{\prime }\in X$. Evaluation at $a\in [0,1]$ is one-Lipschitz because

Choose distinct $a_0,\dots ,a_n\in [0,1]$ and defineThe Vandermonde determinant is nonzero, so $T$ is a bijection. It is one-Lipschitz for the two uniform metrics. If ${\ell }_i$ are the associated Lagrange cardinal polynomials, thenand henceThus $T^{-1}$ is also Lipschitz.

Let ${\hat{\mathcal{P}}}_n$ be the polynomials whose values lie in $[-1,1]$. Its image under $T$ lies in the bounded cube $[-1,1{]}^{n+1}$. It is closed: if $T(p_j)\to v$, then the Lipschitz inverse gives uniform convergence $p_j\to p=T^{-1}(v)$, and passing to the limit pointwise preserves $|p(x)|\le 1$. By the Heine-Borel theorem, $T({\hat{\mathcal{P}}}_n)$ is compact, and the continuous inverse carries compactness back to ${\hat{\mathcal{P}}}_n$. Therefore

The softplus functionis convex becausePart (b) therefore shows that every $\beta \mapsto h(a_i^T\beta )$ is convex. The absolute value function is convex, so $\beta \mapsto |{\beta }_j|$ is convex for every coordinate $j$. Finally, part (a) says that a finite sum of convex functions is convex. Thereforeis convex. The second sum is the L1 norm regularizer.

The scalar logistic loss $u\mapsto -u+\log (1+e^u)$ is strictly convex because its second derivative is $e^u/(1+e^u{)}^2>0$. If $\hat{\beta }$ and $\tilde{\beta }$ are minimizers but $X\hat{\beta }\ne X\tilde{\beta }$, strict convexity of the loss as a function of the fitted vector and convexity of the L1 norm make the objective at their midpoint strictly smaller than the common minimum. This contradiction proves thatfor every pair of solutions.

Solutions to all three questions of the optimisation for data science course of the University of Oxford Part B examination, sat on 7 June 2023. Source: original released PDF, bundle pages 300–303; paper pages 1–4. The original question numbering is retained without reproducing the question statements. Two printing errors on paper page 3 are addressed explicitly in parts 2(c) and 2(f).

Unless a subscript indicates the L1 norm, $\Vert \cdot \Vert$ denotes the Euclidean norm. In Question 1, the regularization weight is $\lambda \ge 0$ and the step size is positive. The big O notation in part 1(d) is interpreted for fixed $x$ as the step size tends to zero, with the necessary subdifferential qualification explained there.

Put $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$. The proximal operator for the L1 norm separates into independent scalar minimization problems:The subgradient optimality condition is $0\in p_i-z_i+\tau \partial |p_i|$. By the subgradient of the absolute value, a positive solution must satisfy $p_i=z_i-\tau >0$, and a negative solution must satisfy $p_i=z_i+\tau <0$. At zero, the subgradient optimality condition holds exactly when $|z_i|\le \tau$. The squared term makes the objective function a strictly convex function, so these cases give its unique minimiser.

Thus the proximal operator is the soft-thresholding operatorConsequently the requested proximal gradient mapping, rather than just the proximal operator, isThe corresponding proximal gradient method update is $x_i^{+}=S_{\alpha \lambda }(x_i-\alpha {\partial }_{i}f(x))$. Small coordinates are set exactly to zero. When $\lambda =0$, the soft-thresholding operator is the identity and the proximal gradient mapping reduces to $\nabla f(x)$.

The first entrance time ${\tau }_K$ is a stopping time, because $\{{\tau }_K\le n\}={\bigcup }_{j=0}^n\{M_j\le -K\}\in {\mathcal{F}}_n$. Before this time $M_n>-K$; at entrance, the bounded increments give $M_{{\tau }_K}>-K-L$. Thus the stopped martingaleis a nonnegative martingale. Here the stopped process is a martingale since its increment is $1_{\{{\tau }_K>n\}}(M_{n+1}-M_n)$, whose conditional expectation given ${\mathcal{F}}_n$ is zero.

The martingale convergence theorem states that a nonnegative martingale converges almost surely to a finite integrable random variable; indeed its expectations are constant, giving the required bound in the L1 norm. Apply this theorem to $(N_n)$. On $\{{\tau }_K=\infty \}$ the stopped process equals the original one at every time. HenceThe overshoot bound is why the assumption of bounded increments matters.

The uniformly integrable martingale convergence theorem states that a uniformly integrable martingale $(U_n)$ has an integrable terminal random variable $U_{\infty }$ such that $U_n\to U_{\infty }$ almost surely and in the L1 norm, andThe last identity follows by passing to the limit of a sequence in $\mathbb{E}[U_m{1}_A]=\mathbb{E}[U_n{1}_A]$ for $A\in {\mathcal{F}}_n$ and $m\ge n$, using convergence in L1.

Part (b)(iii) verifies uniform integrability for $(Z_n)$, soMoreover $|Z_{\infty }|\le L$ almost surely. In this particular problem the common bound also yields convergence in Lp for every finite $p\ge 1$, including convergence in L2: the dominated convergence theorem applies to $|Z_n-Z_{\infty }{|}^p\le (2L{)}^p$. General uniform integrability alone does not assert these higher-power conclusions.

The Peano kernel theorem writes a derivative-based error functional as $L(u)=\int K(t)u^{(r)}(t)dt$, so its bound in the displayed derivative seminorm is at most the L1 norm of the kernel. This is the sharp constant: continuous derivatives can approximate the sign of $K$ in the weighted integral, and integrating them $r$ times produces admissible test functions. If $K$ has one sign, a constant $r$th derivative already attains equality; in particular $\int K=L[x^r/r!]$. This provides a direct exact check on proposed error constants before estimating individual polynomial pieces.

The displayed Poisson integral is the bounded harmonic function on the upper half-plane with continuous boundary values $f(x,0)=e^{-|x|}$. Taking a Fourier transform in $x$ reduces Laplace's equation to ${\hat{f}}_{yy}-s^2\hat{f}=0$, and the bounded solution has multiplier $e^{-y|s|}$. The convolution theorem gives the displayed expression. At frequency zero the transformed function is constant in $y$, not zero: its value is the total boundary integral, two.

The function decays uniformly as $x^2+y^2\to \infty$. For large $y$, use $P_y\le 1/(\pi y)$ and the boundary L1 norm two. When $y$ is bounded and $|x|$ is large, split the convolution into $|t|\le |x|/2$ and its complement: the kernel is small on the first part, and the exponential boundary value is uniformly small on the second. This also distinguishes spatial decay of the harmonic function from decay of its zero-frequency Fourier coefficient.

Assign an arbitrary finite value at the origin. Polar integration and the substitution rule $u=r^2$ reduce the joint L1 norm exactly to $\pi {\int }_0^{\infty }|\sin u|u^{-\alpha }du$. Near zero, $|\sin u|\le u$ gives $u^{1-\alpha }$; at infinity, $|\sin u|\le 1$ gives $u^{-\alpha }$. These are integrable when $\alpha <2$ and $\alpha >1$, respectively. Their explicit integrals give the displayed bound. This is a planar version of sine power kernel integrability, with the radial area element determining the exponents.

The subdifferential of the L1 norm consists of vectors $z$ with $z_j=\mathrm{sgn}({\beta }_j)$ when ${\beta }_j\ne 0$ and $z_j\in [-1,1]$ when ${\beta }_j=0$. These coordinate conditions give the Karush-Kuhn-Tucker conditions for Lasso and Square-root Lasso.

Taxicab geometry equips Euclidean coordinate space with the distance induced by the L1 norm, so the distance between two points is the sum of their coordinatewise absolute differences.

For $f\in L^1(\mathbb{T},m)$ with $m$ normalized Lebesgue measure, translation on the circle group is continuous in the L1 norm: $\Vert f(\cdot +t)-f{\Vert }_1\to 0$ as $t\to 0$ modulo one. Approximate $f$ in the L1 norm by a continuous function, use its uniform continuity, and use translation invariance to preserve the approximation error. In particular, $m(B△(B-t))\to 0$ for every measurable $B$.