text:
algorithms.registration.groupwise_registration¶

Module: algorithms.registration.groupwise_registration¶

Inheritance diagram for nipy.algorithms.registration.groupwise_registration:

Motion correction / motion correction with slice timing

Routines implementing motion correction and motion correction combined with slice-timing.

See:

Roche, Alexis (2011) A four-dimensional registration algorithm with application to joint correction of motion and slice timing in fMRI. Medical Imaging, IEEE Transactions on; 30:1546–1554

Classes¶

FmriRealign4d¶

class nipy.algorithms.registration.groupwise_registration.FmriRealign4d(images, slice_order=None, tr=None, tr_slices=None, start=0.0, interleaved=None, time_interp=None, slice_times=None, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, slice_info=None)
__init__(images, slice_order=None, tr=None, tr_slices=None, start=0.0, interleaved=None, time_interp=None, slice_times=None, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, slice_info=None)

Spatiotemporal realignment class for fMRI series. This class is similar to Realign4d but provides a more flexible API for initialization in order to make it easier to declare slice acquisition times for standard sequences.

Warning: this class is deprecated; please use SpaceTimeRealign instead.

Parameters: images : image or list of images Single or multiple input 4d images representing one or several fMRI runs. slice_order : str or array-like If str, one of {‘ascending’, ‘descending’}. If array-like, then the order in which the slices were collected in time. For instance, the following represents an ascending contiguous sequence: slice_order = [0, 1, 2, …] Note that slice_order differs from the argument used e.g. in the SPM slice timing routine in that it maps spatial slice positions to slice times. It is a mapping from space to time, while SPM conventionally uses the reverse mapping from time to space. For example, for an interleaved sequence with 10 slices, where we acquired slice 0 (in space) first, then slice 2 (in space) etc, slice_order would be [0, 5, 1, 6, 2, 7, 3, 8, 4, 9] Using slice_order assumes that the inter-slice acquisition time is constant throughout acquisition. If this is not the case, use the slice_times argument instead and leave slice_order to None. tr : float Inter-scan repetition time, i.e. the time elapsed between two consecutive scans. The unit in which tr is given is arbitrary although it needs to be consistent with the tr_slices and start arguments if provided. If None, tr is computed internally assuming a regular slice acquisition scheme. tr_slices : float Inter-slice repetition time, same as tr for slices. If None, acquisition is assumed regular and tr_slices is set to tr divided by the number of slices. start : float Starting acquisition time (time of the first acquired slice) respective to the time origin for resampling. start is assumed to be given in the same unit as tr. Setting start=0 means that the resampled data will be synchronous with the first acquired slice. Setting start=-tr/2 means that the resampled data will be synchronous with the slice acquired at half repetition time. time_interp: bool Tells whether time interpolation is used or not within the realignment algorithm. If False, slices are considered to be acquired all at the same time, thus no slice timing correction will be performed. interleaved : bool Deprecated argument. Tells whether slice acquisition order is interleaved in a certain sense. Setting interleaved to True or False will trigger an error unless slice_order is ‘ascending’ or ‘descending’ and slice_times is None. If slice_order==’ascending’ and interleaved==True, the assumed slice order is (assuming 10 slices): [0, 5, 1, 6, 2, 7, 3, 8, 4, 9] If slice_order==’descending’ and interleaved==True, the assumed slice order is: [9, 4, 8, 3, 7, 2, 6, 1, 5, 0] WARNING: given that there exist other types of interleaved acquisitions depending on scanner settings and manufacturers, you should refrain from using the interleaved keyword argument unless you are sure what you are doing. It is generally safer to explicitly input slice_order or slice_times. slice_times : None, str or array-like This argument can be used instead of slice_order, tr_slices, start and time_interp altogether. If None, slices are assumed to be acquired simultaneously hence no slice timing correction is performed. If array-like, then slice_times gives the slice acquisition times along the slice axis in units that are consistent with the provided tr. Generally speaking, the following holds for sequences with constant inter-slice repetition time tr_slices: slice_times = start + tr_slices * slice_order For other sequences such as, e.g., sequences with simultaneously acquired slices, it is necessary to input slice_times explicitly along with tr. slice_info : None or tuple, optional None, or a tuple with slice axis as the first element and direction as the second, for instance (2, 1). If None, then the slice axis and direction are guessed from the first run’s affine assuming that slices are collected along the closest axis to the z-axis. This means that we assume by default an axial acquisition with slice axis pointing from bottom to top of the head.

Image4d¶

class nipy.algorithms.registration.groupwise_registration.Image4d(data, affine, tr, slice_times, slice_info=None)

Bases: object

Class to represent a sequence of 3d scans (possibly acquired on a slice-by-slice basis).

Object remains empty until the data array is actually loaded in memory.

Parameters: data : nd array or proxy (function that actually gets the array)
__init__(data, affine, tr, slice_times, slice_info=None)

Configure fMRI acquisition time parameters.

free_data()
get_data()
get_shape()
scanner_time(zv, t)

tv = scanner_time(zv, t) zv, tv are grid coordinates; t is an actual time value.

z_to_slice(z)

Account for the fact that slices may be stored in reverse order wrt the scanner coordinate system convention (slice 0 == bottom of the head)

Realign4d¶

class nipy.algorithms.registration.groupwise_registration.Realign4d(images, tr, slice_times=None, slice_info=None, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)

Bases: object

__init__(images, tr, slice_times=None, slice_info=None, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)

Spatiotemporal realignment class for series of 3D images.

The algorithm performs simultaneous motion and slice timing correction for fMRI series or other data where slices are not acquired simultaneously.

Parameters: images : image or list of images Single or multiple input 4d images representing one or several sessions. tr : float Inter-scan repetition time, i.e. the time elapsed between two consecutive scans. The unit in which tr is given is arbitrary although it needs to be consistent with the slice_times argument. slice_times : None or array-like If None, slices are assumed to be acquired simultaneously hence no slice timing correction is performed. If array-like, then the slice acquisition times. slice_info : None or tuple, optional None, or a tuple with slice axis as the first element and direction as the second, for instance (2, 1). If None, then guess the slice axis, and direction, as the closest to the z axis, as estimated from the affine.
estimate(loops=5, between_loops=None, align_runs=True, speedup=5, refscan=0, borders=(1, 1, 1), optimizer='ncg', xtol=1e-05, ftol=1e-05, gtol=1e-05, stepsize=1e-06, maxiter=64, maxfun=None)

Estimate motion parameters.

Parameters: loops : int or sequence of ints Determines the number of iterations performed to realign scans within each run for each pass defined by the speedup argument. For instance, setting speedup == (5,2) and loops == (5,1) means that 5 iterations are performed in a first pass where scans are subsampled by an isotropic factor 5, followed by one iteration where scans are subsampled by a factor 2. between_loops : None, int or sequence of ints Similar to loops for between-run motion estimation. Determines the number of iterations used to realign scans across runs, a procedure similar to within-run realignment that uses the mean images from each run. If None, assumed to be the same as loops. The setting used in the experiments described in Roche, IEEE TMI 2011, was: speedup = (5, 2), loops = (5, 1) and between_loops = (5, 1). align_runs : bool Determines whether between-run motion is estimated or not. If False, the between_loops argument is ignored. speedup: int or sequence of ints Determines an isotropic sub-sampling factor, or a sequence of such factors, applied to the scans to perform motion estimation. If a sequence, several estimation passes are applied. refscan : None or int Defines the number of the scan used as the reference coordinate system for each run. If None, a reference coordinate system is defined internally that does not correspond to any particular scan. Note that the coordinate system associated with the first run is always borders : sequence of ints Should be of length 3. Determines the field of view for motion estimation in terms of the number of slices at each extremity of the reference grid that are ignored for motion parameter estimation. For instance, borders==(1,1,1) means that the realignment cost function will not take into account voxels located in the first and last axial/sagittal/coronal slices in the reference grid. Please note that this choice only affects parameter estimation but does not affect image resampling in any way, see resample method. optimizer : str Defines the optimization method. One of ‘simplex’, ‘powell’, ‘cg’, ‘ncg’, ‘bfgs’ and ‘steepest’. xtol : float Tolerance on variations of transformation parameters to test numerical convergence. ftol : float Tolerance on variations of the intensity comparison metric to test numerical convergence. gtol : float Tolerance on the gradient of the intensity comparison metric to test numerical convergence. Applicable to optimizers ‘cg’, ‘ncg’, ‘bfgs’ and ‘steepest’. stepsize : float Step size to approximate the gradient and Hessian of the intensity comparison metric w.r.t. transformation parameters. Applicable to optimizers ‘cg’, ‘ncg’, ‘bfgs’ and ‘steepest’. maxiter : int Maximum number of iterations in optimization. maxfun : int Maximum number of function evaluations in maxfun.
resample(r=None, align_runs=True)

Return the resampled run number r as a 4d nipy-like image. Returns all runs as a list of images if r is None.

Realign4dAlgorithm¶

class nipy.algorithms.registration.groupwise_registration.Realign4dAlgorithm(im4d, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, transforms=None, time_interp=True, subsampling=(1, 1, 1), refscan=0, borders=(1, 1, 1), optimizer='ncg', optimize_template=True, xtol=1e-05, ftol=1e-05, gtol=1e-05, stepsize=1e-06, maxiter=64, maxfun=None)

Bases: object

__init__(im4d, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, transforms=None, time_interp=True, subsampling=(1, 1, 1), refscan=0, borders=(1, 1, 1), optimizer='ncg', optimize_template=True, xtol=1e-05, ftol=1e-05, gtol=1e-05, stepsize=1e-06, maxiter=64, maxfun=None)
align_to_refscan()

The motion_estimate method aligns scans with an online template so that spatial transforms map some average head space to the scanner space. To conventionally redefine the head space as being aligned with some reference scan, we need to right compose each head_average-to-scanner transform with the refscan’s ‘to head_average’ transform.

estimate_instant_motion(t)

Estimate motion parameters at a particular time.

estimate_motion()

Optimize motion parameters for the whole sequence. All the time frames are initially resampled according to the current space/time transformation, the parameters of which are further optimized sequentially.

init_instant_motion(t)

Pre-compute and cache some constants (at fixed time) for repeated computations of the alignment energy.

The idea is to decompose the average temporal variance via:

V = (n-1)/n V* + (n-1)/n^2 (x-m*)^2

with x the considered volume at time t, and m* the mean of all resampled volumes but x. Only the second term is variable when

one volumes while the others are fixed. A similar decomposition is used for the global variance, so we end up with:

V/V0 = [nV* + (x-m*)^2] / [nV0* + (x-m0*)^2]

resample(t)

Resample a particular time frame on the (sub-sampled) working grid.

x,y,z,t are “head” grid coordinates X,Y,Z,T are “scanner” grid coordinates

resample_full_data()
set_fmin(optimizer, stepsize, **kwargs)

Return the minimization function

set_transform(t, pc)

SpaceRealign¶

class nipy.algorithms.registration.groupwise_registration.SpaceRealign(images, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)
__init__(images, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)

Spatial registration of time series with no time interpolation

Parameters: images : image or list of images Single or multiple input 4d images representing one or several fMRI runs. affine_class : Affine class, optional transformation class to use to calculate transformations between the volumes. Default is :class:Rigid

SpaceTimeRealign¶

class nipy.algorithms.registration.groupwise_registration.SpaceTimeRealign(images, tr, slice_times, slice_info, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)
__init__(images, tr, slice_times, slice_info, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>)

Spatiotemporal realignment class for fMRI series.

This class gives a high-level interface to Realign4d

Parameters: images : image or list of images Single or multiple input 4d images representing one or several fMRI runs. tr : None or float or “header-allow-1.0” Inter-scan repetition time in seconds, i.e. the time elapsed between two consecutive scans. If None, an attempt is made to read the TR from the header, but an exception is thrown for values 0 or 1. A value of “header-allow-1.0” will signal to accept a header TR of 1. slice_times : str or callable or array-like If str, one of the function names in SLICETIME_FUNCTIONS dictionary from nipy.algorithms.slicetiming.timefuncs. If callable, a function taking two parameters: n_slices and tr (number of slices in the images, inter-scan repetition time in seconds). This function returns a vector of times of slice acquisition $$t_i$$ for each slice $$i$$ in the volumes. See nipy.algorithms.slicetiming.timefuncs for a collection of functions for common slice acquisition schemes. If array-like, then should be a slice time vector as above. slice_info : int or length 2 sequence If int, the axis in images that is the slice axis. In a 4D image, this will often be axis = 2. If a 2 sequence, then elements are (slice_axis, slice_direction), where slice_axis is the slice axis in the image as above, and slice_direction is 1 if the slices were acquired slice 0 first, slice -1 last, or -1 if acquired slice -1 first, slice 0 last. If slice_info is an int, assume slice_direction == 1. affine_class : Affine class, optional transformation class to use to calculate transformations between the volumes. Default is :class:Rigid

Functions¶

nipy.algorithms.registration.groupwise_registration.adjust_subsampling(speedup, dims)
nipy.algorithms.registration.groupwise_registration.guess_slice_axis_and_direction(slice_info, affine)
nipy.algorithms.registration.groupwise_registration.interp_slice_times(Z, slice_times, tr)
nipy.algorithms.registration.groupwise_registration.make_grid(dims, subsampling=(1, 1, 1), borders=(0, 0, 0))
nipy.algorithms.registration.groupwise_registration.realign4d(runs, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, time_interp=True, align_runs=True, loops=5, between_loops=5, speedup=5, refscan=0, borders=(1, 1, 1), optimizer='ncg', xtol=1e-05, ftol=1e-05, gtol=1e-05, stepsize=1e-06, maxiter=64, maxfun=None)
Parameters: runs : list of Image4d objects transforms : list nested list of rigid transformations transforms map an ‘ideal’ 4d grid (conventionally aligned with the first scan of the first run) to the ‘acquisition’ 4d grid for each run
nipy.algorithms.registration.groupwise_registration.resample4d(im4d, transforms, time_interp=True)

Resample a 4D image according to the specified sequence of spatial transforms, using either 4D interpolation if time_interp is True and 3D interpolation otherwise.

nipy.algorithms.registration.groupwise_registration.scanner_coords(xyz, affine, from_world, to_world)
nipy.algorithms.registration.groupwise_registration.single_run_realign4d(im4d, affine_class=<class 'nipy.algorithms.registration.affine.Rigid'>, time_interp=True, loops=5, speedup=5, refscan=0, borders=(1, 1, 1), optimizer='ncg', xtol=1e-05, ftol=1e-05, gtol=1e-05, stepsize=1e-06, maxiter=64, maxfun=None)

Realign a single run in space and time.

Parameters: im4d : Image4d instance speedup : int or sequence If a sequence, implement a multi-scale realignment
nipy.algorithms.registration.groupwise_registration.tr_from_header(images)

Return the TR from the header of an image or list of images.

Parameters: images : image or list of images Single or multiple input 4d images representing one or several sessions. float Repetition time, as specified in NIfTI header. ValueError if the TR between the images is inconsistent.


text:
# How does this integration work when solving a DE?

$\def\d{\mathrm{d}}$I understand what differential equations are and what they are useful for. They're very interesting, but I'm not quite sure what is going on when actually solving one.

This is what I'm trying to solve:

$$\frac{\d y}{\d x} = 2y + 3.$$

As far as I know, this is a first-order linear ordinary differential equation. Seems fairly simple.

The first step that I am told to do is to 'separate the variables'. So I multiply both sides of the equation by $\d x$ and then divide both sides by $2y + 3$ to end up with:

$$\frac{\d y}{2y+3} = \d x.$$

So now I've got all of my $y$ terms on one side, and all of my $x$ terms on the other.

The fact that I can split apart the $\frac{\d y}{\d x}$ does seem a bit strange to me, but I'm told that it's sensible and I'm willing to believe, for now, that that's an OK thing to do.

After this, I'm told to 'integrate both sides' and I'm shown this as the next step:

$$\int \frac{\d y}{2y+3} = \int \d x$$

Normally when integrating, I would denote the 'integral of [integrand] with respect to $x$' using the standard notation:

$$\int \text{[integrand]}\,\d x$$

In definite integration, the $\int$ represents an infinite sum, and the $\d x$ represents, as usual, a very small change in $x$ that is being multiplied by the value of the function at that point in order to, as $\d x$ approaches zero, generate the exact value of the area under the curve.

For now I will just accept that we also write it in this fashion when doing indefinite integration. However, the second step in the solution to the DE confuses me because it doesn't seem to follow this notation.

If you want to integrate both sides, then that means we must be integrating $\d x$ on the right hand side. If this is true, then I would normally write it as $\int \d x\,\d x$, because it is the integral of $\d x$ with respect to $x$. However, in the solution it simply shows $\int \d x$ as if we have lost the $\d x$ that we would have put in as notation.

The other side of the equation also doesn't have a $\d y$ at the end, as I would expect it to.

My real question is: What do $\d x$ and $\d y$ represent on their own? I understand that $\dfrac{\d y}{\d x}$ represents the derivative of $y$ with respect to $x$, and that it is representing an instantaneous rate of change because it is essentially representing an infinitesimally small change in $y$, divided by an infinitesimally small change in $x$ (the gradient at a point).

However, when I see something like $\d x$ on its own, I'm not sure what the meaning of it is any more. It's an infinitesimally small change in $x$, right? How do we integrate that? What does it mean? I want to be very clear that I'm not asking someone to walk me through solving it, because the web is full of examples of solving these types of equations. I'd be much more grateful for a conceptual answer to my question.

And as an extra question: How does integrating both sides of an equation with respect to different variables make sense? Surely the two sides would no longer be equal.

• Good question. You'll find some useful information in these posts: math.stackexchange.com/a/27433/159845, math.stackexchange.com/a/182352/159845 & math.stackexchange.com/a/1252426/159845 – StackTD Apr 20 '17 at 9:28
• Please have a look at this post, of which yours may be a duplicate. – Harry49 Apr 20 '17 at 9:29
• @StackTD Thank you, but none of those posts seem to answer my exact question. I'm asking specifically why the usual trailing $dx$ is lost on the right hand side when integrating with respect to $x$. – 雨が好きな人 Apr 20 '17 at 17:43
• But it's not missing. The wrangling that you did to get the terms to each side restructured things so you are essentially taking the integral of $\frac{1}{2y+3}$ with respect to y on the left and the integral of 1 with to x on the right. – scrappedcola Apr 20 '17 at 19:05

In this question, we actually don't need to ponder what $\newcommand{\D}{\mathrm{d}} \D y$ and $\D x$ mean individually (in terms of differential forms, etc.). Instead, this splitting apart of $\D y \over \D x$ can be justified in the following more rigorous manner. After separating variables, you have the equation

$$\frac{1}{2y(x) + 3} \frac{\D y}{\D x} = 1 \quad \text{or} \quad \frac{1}{2y(x) + 3} y'(x) = 1$$ where we should keep in mind that $y$ is a function of $x$ (dependent / independent variables). Now, we integrate both sides with respect to $x$:

$$\int \frac{1}{2y(x) + 3} \frac{\D y}{\D x} ~\D x=\int \frac{1}{2y(x) + 3} y'(x) ~\D x = \int 1~\D x.$$

Observations:

1. For the right hand side, we recognize that $\int ~\D x = \int 1 ~\D x$. This is where that missing integrand you referred to goes. These truly give the same anti-derivative. In higher math, $\int \D x$ is probably preferred, but this requires training in something like differential geometry / differential forms / tensor calculus / calculus on manifolds.
2. For the left hand sides, we can recognize this as the integral of a chain rule. Taking the total differential of $y(x)$ gives $$dy = \frac{\D y}{\D x} \D x = y'(x) \D x.$$ Thus the left hand side becomes $$\int \frac{1}{2y + 3} ~\D y.$$ If you prefer, you can think of this a $u$-sub: let $u(x) = y(x) \implies \D u = \D y = \frac{\D y}{\D x} \D x$ and the integral becomes $$\int \frac{1}{2u + 3} ~\D u.$$

What's going on is that the Leibniz notation for calculus is a little too good---many of the standard calculus rules appear to just be manipulating fractions. For example,

• $u$-sub with Leibniz: $\int f(u(x)) \frac{\D u}{\D x} ~\D x = \int f(u) ~\D u$. This almost looks like we just cancel the "$\D x$".
• Chain rule with Leibniz: $\frac{\D y}{\D t} = \frac{\D y}{\D x}\frac{\D x}{\D t}$.
• Total differential with Leibniz: $\D y = \frac{\D y}{\D x} \D x = y'(x) \D x$.
• Stokes' Theorem: $\int_{\partial M} \omega = \int_M \D \omega$.

Despite how suggestive this notation is, you should always keep in mind that $\frac{\D y}{\D x}$ is not really a fraction. However, it does behave like a fraction in many ways and this can be a useful way to remember these calculus properties.

### General Separable Problem

Given a separable differential equation

$$f(y(x)) \frac{\D y}{\D x} = g(x)$$

we integrate both sides with respect to $x$ to get

$$\int f(y(x)) \frac{\D y}{\D x} ~\D x = \int g(x)~ \D x.$$

As above, we recognize the left hand side as the result of a chain rule / a $u$-sub integral to get $$\int f(y) ~\D y = \int g(x) ~\D x.$$

Note that this gets us to the same place as if we had split up $\D y \over \D x$ to begin with: \begin{align*} f(y) ~\frac{\D y}{\D x} &= g(x) \\ f(y) ~\D y &= g(x) ~\D x\\ \int f(y) ~\D y &= \int g(x) ~\D x. \end{align*} While this second version should make a mathematician a little squeamish, it is justified in this case by our reasoning above and is a useful computational shortcut.

If you really want to know what $\D x$ and $\D y$ truly mean, this Introduction to Differential Forms gives a good overview, written for an undergraduate audience (multivariable calculus as only prerequisite). The glib answer is that $\D x$ returns the $x$ component of a vector...

format: plain


text:
# Linear space of translatable functions.

What are the functions $f$ so that a set $\{a \cdot f(x+b) : a \in \mathbb{R}, b \in \mathbb{R}\}$ is a finite dimensional linear vector space ?

Is there a complete characterization of such functions?

$e^{c x}$ (where $c$ is some constant) is a good example of a base of one dimensional space.
$sin (c x), cos(c x)$ seems to be two dimensional example.

• Please rephrase the title or question if you know proper mathematical names. – Łukasz Lew Aug 19 '10 at 15:26
• Unless I misunderstand your notation, $f(x) = e^x$ is a function such that the set you want is a one-dimensional vector space. And thus trivially it has a finite-dimensional dense subspace. – Willie Wong Aug 19 '10 at 16:01
• I'm trying to expand my understanding of Fourier transform. – Łukasz Lew Aug 19 '10 at 16:19

The question, as stated, is about the set of multiples of translates, but from the example quoted, $\sin x,$ I suspect that OP really meant the span.

Theorem Let $f$ be a continuous complex-valued function on $\mathbb{R}.$ Then the following conditions are equivalent:

1. The translates $\{f(x+b) : b\in\mathbb{R}\}$ span a finite-dimensional vector space;

2. $f$ satisfies a homogeneous constant coefficient linear differential equation;

3. $f$ is a finite linear combination of functions $f_{k,\lambda}(x)=x^k e^{\lambda x}.$

Proof. If $f$ is assumed infinitely differentiable then all derivatives of $f$ belong to the $\mathbb{R}$-span of translates of $f.$ Thus condition 1 implies that $f$ and its derivatives of order up to $n$ are linearly dependent over $\mathbb{R},$ which is condition 2. The smoothness assumption may be removed by using the Fourier or Laplace transform.

The equivalence of conditions 2 and 3 is a basic fact of ODEs. Finally, a direct computation shows that $f_{k,\lambda}(x)$ spans the $(k+1)$-dimensional vector space $\{P(x)e^{\lambda x}: P\text{ is a polynomial of degree} \leq k\}$, so condition 3 implies condition 1. $\square$

Condition 1 – 3 have the following representation-theoretic interpretation. The additive group of $\mathbb{R}$ acts on itself by the right multiplication. This gives rise to a linear representation of $\mathbb{R}$ on the functions on $\mathbb{R}$ via translations called the right regular representation, and condition 1 states that $f$ belongs to a finite-dimensional subrepresentation $V$. Finite-dimensionality of $V$ implies that $V$ contains an irreducible subrepresentation $W$, which must be one-dimensional (Schur's lemma), hence $W$ is spanned by a character of $\mathbb{R}.$ All continuous characters are the exponential functions $e^{\lambda x}$ for various $\lambda\in\mathbb{C}$; however, using a Hamel basis of $\mathbb{R},$ it is easy to see that there are uncountably many others.

Condition 2 is the Lie algebra analogue of condition 1: viewing $\mathbb{R}$ as a one-dimensional Lie group, the content of Lie's theorem is that its finite-dimensional (continuous) representations correspond (by differentiation and exponentiation) to f.d. representations of the abelian one-dimensional Lie algebra, i.e. to a single linear transformation on $V.$ The span $V_{n,\lambda}$ of the functions $f_{k,\lambda}$ with $0\leq k\leq n-1$ from condition 3 is an $n$-dimensional indecomposable representation of $\mathbb{R},$ whose infinitesimal version is a Jordan block of order $n$ with $\lambda$ on the diagonal. Moreover, any subrepresentation isomorphic to $V_{n,\lambda},$ i.e. corresponding to the same Jordan block, must be $V_{n,\lambda}$ itself.

• Since OP's literal formulation implies that $f$ satisfies condition 1, one easily concludes that the requisite $f$ must be a constant multiple of $e^{\lambda x}$. – Victor Protsak Aug 19 '10 at 19:46
• I thought at first, after seeing the $sin(x)$ example, that span was what was meant. But now I am not too sure after thinking about it for a bit. The identity $a \sin(x) + b \cos(x) = \sqrt{a^2 + b^2}\sin(x + c)$ where $\sin c = b / \sqrt{a^2 + b^2}$ (assuming $a$ positive) implies that for the case of $\sin$, the span and the set are equal. – Willie Wong Aug 19 '10 at 20:04
• Willie, you need both $\sin x$ and $\cos x$ to make it translation invariant. Put differently, $\sin x$ is a linear combination of $e^{ix}$ and $e^{-ix}$ with non-zero coefficients, so the space spanned by its translates is 2-dimensional. – Victor Protsak Aug 19 '10 at 20:48
• I agree that the vector space is spanned by sin(x) and cos(x), but since cos(x) is just a translate of sin(x) anyway, isn't the vector space generated just by the translations and dilations of sin(x) only, as the OP intended? (I have a slight suspicion that this discussion between us is just about semantics.) In other words, I can write $V = \{ a \sin(x) + b \cos(x) : a,b\in R\}$ or $V = \{ a \sin(x + b): a,b\in R\}$ and refer to the same thing? – Willie Wong Aug 19 '10 at 22:14
• You are absolutely right! I am sorry, I didn't think through your first comment. So a real-valued continuous function $f$ of real argument has the property that its dilated translates form a f.d. vector space if and only if $f(x)=e^{\lambda x}(A\cos\omega x+B\sin\omega x).$ – Victor Protsak Aug 20 '10 at 2:08

Not a complete answer but I think this might be a good start, at least in the special case when $f$ is a smooth function.

Since you require that the set is a vector space, the ratio $h^{-1}(f(x+h)-f(x))$ must belong to it and hence must be of the form $a_h f(x+b_h)$ for some $a_h,b_h$ depending on $h$. Since we are assuming that $f(x)$ is differentiable, the limit of $a_h f(x+b_h)$ as $h\to0$ exists and is precisely $f'(x)$, for every $x$. Take subsequences so that $a_h$ and $b_h$ have a (possibly infinite) limit. Now there are several cases to consider, depending on the combination of limits we get. Let us restrict to the case $a_h\to a$, $b_h\to b$ for some finite reals $a,b$ (I told you this is just a start). Then the function $f$ must satisfy the delay ODE

$$f'=a f(x+b).$$

When $b=0$ you get your exponentials. When $b=\pi/2$ you get $\sin$ and $\cos$. For other values of $b$: this is a well studied class of equations and it's easy to find pointers (keyword: delay ODE). Or solve by hands...

EDIT: this argument does not use the assumption that the space is finite-dimensional :) Let's say it is a nice complement to the much more polished answer by Victor

So for $f(x)=x^2$ one has $$f(x+b)=(1-b^2)f(x)+\frac{b^2+b}{2}f(x+1)+\frac{b^2-b}{2}f(x-1)$$ And similarly, $x^k$ (or any polynomial of degree $k$) gives a dimension $k+1$ example. The same goes for $x^ke^x$.

edit As pointed out, these are examples where the span of all the $af(x+b)$ has finite dimension, however it is strictly larger than that set.

• I think you have the relation the other way around? For $f(x) = x^2$, let $a_1 = 1, b_1 = 0, a_2 = -1, b_2 = 1$, then $f_1(x) = a_1f(x + b_1) = x^2$ and $f_2(x) = a_2 f(x + b_2) = -(x+1)^2 = - x^2 - 2x - 1$. $f_1$ and $f_2$ are in the set defined by the OP. But $g = f_1 + f_2 = - 2x - 1$ is not in the span of rescalings and translations of $f(x)$. In fact, by modifying the argument I just wrote down, you can see that for $f(x)$ polynomial the resulting set is not a vector space. – Willie Wong Aug 19 '10 at 19:15


text:
# Fourier transform of $x^\alpha$

Define $\hat{f}(\xi)\equiv F(f)(\xi):=\int_{\mathbb{R}}e^{ix.\xi}f(x)dx$

My question is: if we consider $x^{\alpha}$ as a distribution then what is $F(x^{\alpha})(\xi)$ where $0<\alpha\in\mathbb{R}$. thanks

-
Praise the lord Wolfram!! wolframalpha.com/input/?i=FourierTransform+x^5 –  yohBS Feb 13 '12 at 7:16
@steven how do you define $x^{\pi}$ for $x<0$? –  Andrew Feb 13 '12 at 7:56
The distribution defined by $x^\alpha$ (supported on $\mathbb R_{>0}$) is an example of a homogeneous distribution of degree $\alpha$. It is pretty clear (if you use proper notation) that the Fourier transform of a homogeneous distribution of degree $\alpha$ on $\mathbb R^n$ is homogeneous of degree $-\alpha-n$. To get everything exactly correct requires some work. This stuff is well known and should be in most/many books on distribution theory. E.g., see Vol I of Hormander's book "The Analysis of Linear Partial Diff. Ops", Example 7.1.17. –  B R Apr 14 '12 at 1:37
According to Maple, for positive integer $k$, the Fourier transform of $x^k$ is a certain constant multiple of the $k$th derivative of the Dirac delta function. (Start with the Fourier transform of the constant 1 as $2\pi$ times the delta function, then use the rule on how multiplying by $x$ corresponds to differentiating the transform.) –  GEdgar May 15 '12 at 2:53


text:
Eigenvalues of Krylov matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:41:29Z http://mathoverflow.net/feeds/question/80184 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80184/eigenvalues-of-krylov-matrices Eigenvalues of Krylov matrices Anadim 2011-11-06T02:54:49Z 2011-11-06T16:56:00Z
Let an $n\times n$ matrix ${\bf A}$, the all ones vector ${\bf w}$, and the $n\times n$ Krylov matrix $${\bf K}_n = \left[ {\bf w}\;\;{\bf A}{\bf w}\;\;\ldots \;\; {\bf A}^{n-1}{\bf w}\right].$$ Is there a way to characterize the spectrum of ${\bf K}_n$ in terms of the eigenvalues of ${\bf A}$?
 http://mathoverflow.net/questions/80184/eigenvalues-of-krylov-matrices/80187#80187 Answer by Robert Israel for Eigenvalues of Krylov matrices Robert Israel 2011-11-06T04:24:59Z 2011-11-06T04:24:59Z
Certainly not in terms of the eigenvalues of $A$, because this won't be invariant under similarity transformations on $A$. One thing I can say is that for any vector $b$, $K b = \sum_{j=0}^{n-1} b_{j+1} A^j w$. So $K$ is singular if and only if $w$ is in the null space of a nontrivial polynomial in $A$ of degree $\le n-1$.
 http://mathoverflow.net/questions/80184/eigenvalues-of-krylov-matrices/80188#80188 Answer by Faisal for Eigenvalues of Krylov matrices Faisal 2011-11-06T04:25:30Z 2011-11-06T04:25:30Z
I don't see any reason for there to be a nice characterization. For instance if $A$ is diagonal then $K_n$ is a Vandermonde matrix, so its spectrum is fairly complicated...
 http://mathoverflow.net/questions/80184/eigenvalues-of-krylov-matrices/80224#80224 Answer by Nilima Nigam for Eigenvalues of Krylov matrices Nilima Nigam 2011-11-06T16:56:00Z 2011-11-06T16:56:00Z
The short answer is: no. You can see the difficulty if $w$ is an eigenvector of $A$:the Krylov matrix becomes singular, while $A$ may not be.

The Krylov matrix is generated, as you probably know, during the Arnoldi iteration for locating eigenvalues of A. As part of the (stabilized version) of the process, A is partially reduced through orthogonal projections onto $\cal{K}_n$ to Hessenberg form, $H_n$. The eigenvalues of $H_m$, \$m


text:
MathSciDoc: An Archive for Mathematician ∫

Analysis of PDEsCombinatoricsFunctional Analysismathscidoc:1701.03005

Acta Mathematica, 207, (2), 255-290, 2009.12
An analogue of the well-known $$\frac{3}{{16}}$$ lower bound for the first eigenvalue of the Laplacian for a congruence hyperbolic surface is proven for a congruence tower associated with any non-elementary subgroup$L$of SL(2,$Z$). The proof in the case that the Hausdorff of the limit set of$L$is bigger than $$\frac{1}{2}$$ is based on a general result which allows one to transfer such bounds from a combinatorial version to this archimedian setting. In the case that delta is less than $$\frac{1}{2}$$ we formulate and prove a somewhat weaker version of this phenomenon in terms of poles of the corresponding dynamical zeta function. These “spectral gaps” are then applied to sieving problems on orbits of such groups.
@inproceedings{jean2009generalization,
title={Generalization of Selberg’s $$\frac{3}{{16}}$$ theorem and affine sieve},
author={Jean Bourgain, Alex Gamburd, and Peter Sarnak},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203357420511746},
booktitle={Acta Mathematica},
volume={207},
number={2},
pages={255-290},
year={2009},
}

Jean Bourgain, Alex Gamburd, and Peter Sarnak. Generalization of Selberg’s $$\frac{3}{{16}}$$ theorem and affine sieve. 2009. Vol. 207. In Acta Mathematica. pp.255-290. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170108203357420511746.


text:
## On a functional equation of Alsina and García-Roig.(English)Zbl 0912.39010

The author determines, for every fixed $$p \in ]0,1[$$, the general solution $$f : I \to {\mathbb R}$$ of the functional equation $f(px + (1-p)y) f((1-p)x + py) = f(x) f(y) \qquad (x,y \in I),$ supposing that $$f$$ is different from zero on a set of positive Lebesgue measures. The main theorem (Theorem 2) provides a generalization of a result of W. Jarczyk and M. Sablik [Result. in Math. 26, No. 3-4, 324-335 (1994; Zbl 0829.39008)].

### MSC:

 39B22 Functional equations for real functions

Zbl 0829.39008


text:
• Notice: Please see part 1 for an introduction to this project.
• Repository for this project: Github
• python file for training ConvNet: FCN512_2.py
• Jupyter notebooks used for image learning and plots: Learn_image.ipynb, Generate_plots.ipynb

In Brief

• In deep generative modeling, Texture synthesis is the process of creating novel texture images. Texture extraction involves taking a natural image and producing images with qualitatively similar texture properties.
• In this project, I develop a novel texture extraction model that uses image-learning-based techniques. This make it similar to something like the original neural style transfer process. However, I employ a texture descriptor based on global average pooling across convolutional channels. This descriptor effectively captures how all convolutional filters in a (pre-trained) fully convolutional network (FCN) are activated. I first train a generative FCN (structured like an autoencoder) on a lichen photo dataset that I created. I then iteratively optimize a texture image until its texture descriptor vector matches that of a target image.
• Research question: 1. How does my novel texture descriptor perform?–what will the synthetic images derived from it look like? 2. What effect does the FCN’s training data have on the textures generated?
• Result: When learning a new texture image, my model captures the color distribution of the target image well. The spatial features in the learned image do not reflect those in the target image very well. However, the nature of the training data had an obvious impact on the appearance of textures that could be generated.
• In part 1/2: I’ll give a broad overview of the different paradigms in deep generative modeling, as well as some alternative texture extraction models from the literature that had better performance. This is useful since it classifies my own model and contrasts it with fundamentally different methods such as GANs.
• In part 2/2 (this post): I’ll cover my dataset, network architecture, image learning algorithm, and results.

# Research Objective

Is it possible to take a natural image and “extract” the textures within it? I.e Can we generate images containing new instances of those textures? This texture synthesis, or more specifically, texture extraction is one of many challenging computer vision tasks that has been advanced substantially in recent years by convolutional neural networks (CNNs). The authors of Learning Texture Manifolds with the Periodic Spatial GAN describe it this way

The goal of texture synthesis is to learn from a given example image a generating process, which allows to create many images with similar properties.

In this project I develop and evaluate a novel texture extraction method that is image-learning-based, meaning we optimize (learn) the pixel values of an image directly by iteratively applying gradients to the image. My procedure is in the same spirit as convolutional filter visualization, neural style transfer, or DeepDream.

I ask whether a novel texture descriptor based on global average pooling across all convolutional channels can capture qualitative features of the texture in a target image. I also ask how the original data that the network was trained on affect the textures that can be generated.

# Brief Methods

There are two main steps in the pipeline. The first involves training a fully convolutional network (FCN), that is set up like an autoencoder, to take input texture images and reconstruct them. This forces the network to learn meaningful feature detectors (i.e. convolutional filters) that can later be used to represent the texture of a new image (that I call the “target” image).

The second step is to run the algorithm that, starting from an initial condition of noise, learns a new image $$Z$$. The texture of the learned image $$Z$$ is intended to match that of a target image $$A$$. The learned image is iteratively updated in such a way that its texture descriptor (called the “global average pooling (GAP) vector” $$z$$) approaches that of the target image’s texture descriptor, $$a$$. The GAP vectors are computed by sending an image through the FCN and individually pooling the feature maps at all convolutional layer channels (See Figure GAP). After image learning, when fed into the FCN, Z should activate the network’s filters in a similar way as A.

In the next sections I’ll first cover the dataset and training process for step 1, and then explain the texture extraction algorithm.

# Dataset

I constructed the training data from 148 macro photos of lichen that I had taken while travelling across the United states (mostly Arizona and Washington). In order to focus on textures, each training image was partitioned into some number of non-overlapping square sub-images with sizes ranging from ~300x300 to ~600x600. During training all were resized to 512x512x3 pixel patches, for a total of 4323 patches (1.92GB). I did not use any data augmentation but rotating by multiples of $$90^\circ$$ would be reasonable for these type of images. Screenshots of the patches are below.

# Fully convolutional net architecture and training

The FCN is trained exactly like an autoencoder. Batch gradient descent is used to minimize the mean squared error between the pixels of the input image and the reconstructed output image. A key difference here is that there are no pooling layers. For the end-purposes of this model, there does not seem to be a reason to compress the input information through a bottleneck. I kept the same spatial dimensions all the way through for simplicity. This network does not just learn an identity mapping, where the image is copied over and over until the output. As we will see later, the convolutional filters learned have a great impact on the textures that can be generated. Below you can find more details on the layers such as kernel sizes and strides.

FCN_input = keras.Input(shape=(512, 512, 3), name='FCN_input')
x = layers.Conv2D(32, 7, strides=(1, 1), activation='relu', padding='same')(FCN_input)
x = layers.Conv2D(32, 7, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.BatchNormalization(axis=-1)(x)
x = layers.Conv2D(64, 5, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.Conv2D(64, 5, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.BatchNormalization(axis=-1)(x)
x = layers.Conv2D(64, 3, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.Conv2D(64, 3, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.BatchNormalization(axis=-1)(x)
x = layers.Conv2D(64, 1, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.Conv2D(64, 1, strides=(1, 1), activation='relu', padding='same')(x)
x = layers.BatchNormalization(axis=-1)(x)
FCN_output = layers.Conv2D(3, 1, strides=(1, 1), activation='relu', padding='same')(x)
FCN = keras.Model(FCN_input, FCN_output, name='FCN')

Dataset Loss Batch size Optimizer input size # parameters
4323 RGB images, 1.92GB Mean squared error. Unsupervised training (ground truth = input) 8 Adam, learning rate = 0.001 512 x 512 x 3 Trainable: 148387, Non-trainable: 448

Fig GAP. FCN architecture and GAP feature vector. Blue boxes are convolutional layers and green are batch norm layers. NOTE: batch norm layers are drawn as thin slices to save space, but their output has the same shape as the preceding layer. The GAP vector is taken by performing global average pooling of all convolutional layer channels. This produces one vector element per channel. The full vector is a concatenation of all such GAP values.

Fig. Tensorflow model summary

# Image-learning Algorithm

The trained FCN model will be denoted as a function $$F$$, and its output at layer $$l$$ is denoted $$F^{(l)}(X)$$, where $$X$$ is an input image. $$F^{(l)}(X)$$ is a tensor containing $$d^{(l)}$$ feature maps. I equivalently call it $$Y^{(l)} \equiv F^{(l)}(X)$$. For each $$Y^{(l)}$$, we compute the GAP vector segment $$g^{(l)} \in \mathbb{R}^{d^{(l)}}$$ by taking the average of all pixels in each channel. This happens in the function called “GAPL()” in the Algorithm 1 below. Then, the function “GAPVector()” in Algorithm 1 simply concatenates all layers’ $$g^{(l)}$$, resulting in the full GAP texture descriptor.

The texture extraction process is framed in my case as an image optimization problem. We compute a loss $$L$$ based on the mean squared error between the GAP descriptors $$z, a$$ of learned image $$Z$$ and target image $$A$$. I ran the for loop for n=15 iterations. By that point, the learned image had more or less stabilized. At each iteration gradient descent of the loss function is performed by subtracting a gradient tensor $$\nabla_{bfgs}L(Z)$$ from $$Z$$. Note that this gradient is the exact same shape as $$Z$$. $$\nabla_{bfgs}L(Z)$$ denotes the gradient of the loss function with respect to the pixel values in $$Z$$. This gradient is computed using the Limited-memory BFGS optimization algorithm. After the gradient is applied, we send the new image through the network and re-compute its descriptor $$z$$. The cycle then repeats (See Algorithm 1).

Symbol Meaning
Z learned image
A target image
z full GAP descriptor for Z
a full GAP descriptor for A
$$Y^{(l)}$$ all feature maps for layer l
$$F^{(l)}(X)$$ the model’s output at layer $$l$$, given input image $$X$$. (Equivalent to $$Y^{(l)}$$)
L loss value
$$g^{(l)}$$ GAP vector for layer l
$$l$$ layer index
$$d^{(l)}$$ # channels in layer l
m # layers in network
$$\nabla_{bfgs}L(Z)$$ gradient of loss w.r.t. Z from bfgs algorithm
$$Z_{noise}$$ noise image with same size as Z (initial condition)
$$h^{(l)}$$ feature map height spatial dim
$$w^{(l)}$$ feature map width spatial dim

Fig. Algorithm pseudocode

Excerpt from Learn_image.py

outputs_dict = dict([(layer.name, layer.output) for layer in FCN.layers[1:]]) # creates a dict of layer outputs that can be easily accessed to get intermediate outputs

def get_GAP(layer_output):
#input is a (height, width, channels) tensor. We first permute_dimensions to (channels, height, width). Then take the sum over all pixels in each channel.
#each element j of the output is the mean across all pixels in the channel j
return K.mean(K.batch_flatten(K.permute_dimensions(layer_output,(2,0,1))), axis=1)

GAP_target_img = []
GAP_learned_img = []

# cycle through all non-batch norm layers and concat the GAP into one long vector with length equal to the number of channels in the entire network
for name in outputs_dict:
if name.find('batch_normalization') == -1: # skip batch norm layers
layer_features = outputs_dict[name]
GAP_target_img.append(get_GAP(layer_features[0]))
GAP_learned_img.append(get_GAP(layer_features[1]))

GAP_target_img = K.concatenate(GAP_target_img, axis=0)
GAP_learned_img = K.concatenate(GAP_learned_img, axis=0)
GAP_learned_img

Loss = K.sqrt(K.sum(K.square(GAP_target_img-GAP_learned_img)))

# Results and Discussion

I first tested the ability of the trained FCN to reconstruct images. In the figure below, I passed both training images and natural images not from the lichen dataset through the model, and I found that both could be reconstructed well. While this certainly shows that that the model has not been overfit, it begs the question of whether the model has actually learned meaningful feature detectors. For example, the model might be performing an identity mapping in which the input is simply copied over and over. This is something I did not investigate yet. I believe that the lack of pooling layers prevented information from being lost, and this is part of the reason why the reconstructions are so close to the inputs.

In the figure below, I synthesized texture images from 4 training images and 4 natural images not from the training set. My algorithm optimizes an image such that it produces a similar GAP descriptor as a target image. Thus, the ‘Texture’ images appear the same, from the perspective of the GAP descriptor, as the ‘Original’ images. Since each vector element of the GAP descriptor pools across the spatial dimensions of a channel, spatial information is lost. For this reason it’s impossible to recover more complex or larger scale structures seen in the training images.

## Why do the textures look like that and not something else?

The textures synthesized are not random noise. They are not arbitrary—there is a specific reason they look this way.

Each element of the GAP vector measures only the degree to which a particular filter was activated. In other words, a higher value at $$z_j$$ indicates greater presence of the image feature detected by filter $$j$$. The visual appearance of the texture is thus heavily influenced by the types of image features that the network saw during training. For example, if you were perform the same process using VGG net trained on the imagenet dataset, the texture would look completely different. In summary, the textures produced by my network look vaguely like the lichen images it was trained on, and this makes sense. You are asking a network that has been trained to detect certain types of features to produce images containing those features.

## Using the GAP vector as a feature vector in clustering and dimensionality reduction

Finally, for the sake of testing its application as a feature vector, I performed t-SNE dimensionality reduction on a set of GAP vectors. The dataset (a subset of the training data), containing patches from three full-sized images is shown below. I embedded the GAP vector of each image into a 2D space and annotated each point with its patch. The code for this can be found in Generate_plots.ipynb


text:
# XIIIth Quark Confinement and the Hadron Spectrum

31 July 2018 to 6 August 2018
Maynooth University
Europe/Dublin timezone

## Spontaneous Symmetry Breaking in the U(2) Planar Thirring Model?

2 Aug 2018, 15:30
30m
Hall D (Arts Bldg.)

### Hall D

#### Arts Bldg.

Talk G: Strongly Coupled Theories

### Speaker

Prof. Simon Hands (Swansea University)

### Description

Whether the U(2N) symmetry of Dirac fermions in 2+1 space-time dimensions is spontaneously broken by pair condensation once interactions are present is an important problem in non-perturbative quantum field theory. Here I focus on the Thirring model, whose interaction is a current-current contact term, using numerical simulations of a lattice model formulated with domain wall fermions - it has been demonstrated that U(2N) symmetry is recovered in the limit of infinite wall separation. I present results obtained with flavor numbers N=0, 1 and 2, and will attempt to put both upper and lower bounds on $N_c$, the critical number of flavors above which symmetry breaking does not occur even for arbitrarily strong coupling. The resulting $N_c$ will be shown to be very far from the value $N_c\approx6.6$ obtained with staggered lattice fermions, which not observe U(2N) symmetry.

### Primary author

Prof. Simon Hands (Swansea University)

### Presentation Materials

 maynooth_hands.pdf maynooth_hands.pdf


text:
# Natural deduction: how to prove the argument below

Sorry my title is a bit vague, but I have a specific problem I'm trying to solve.

$$P \rightarrow Q \vdash \lnot(P\land\lnot Q)$$

I need to prove this using natural deduction, I can do it using equivalent symbols in propositional logic, but I can't seem to figure out where to even begin in terms of natural deduction.

I (mostly) understand the introduction and elimination rules for connectives, but I just don't know what to do here. I know I've got to turn the premise into the conclusion step by step using introduction and elimination of these logical connectives, but how?

• By "natural deduction" I assume you are looking for a proof "by contradiction". That is, starting from $P \to Q$ and the hypothesis $(P \land \lnot Q)$, produce a contradiction. This seems a straightforward exercise. – hardmath Nov 18 '16 at 13:23
• Would you mind showing me how? I've got: $$1. P \rightarrow Q$$ $$2. \lnot P \lor Q$$ Using Implication elimination rule How do I get to the next step – Shiny_and_Chrome Nov 18 '16 at 14:59
• Instead you want: $$2. P \land \lnot Q$$ When this leads to a contradiction, you will be able say you've done the natural deduction proof. – hardmath Nov 18 '16 at 15:04
• Ok, from my understanding of propositional logic and truth tables, I understand why this is a contradiction and how that proves the original statement, but how do I show that in a natural deduction proof? E.g. $$P \land \lnot Q, Q \lor R \vdash R \lor S$$ $$1. P \land \lnot Q$$ $$2. Q \lor R$$ $$3. \lnot Q$$ $$4. R$$ $$5. R \lor S$$ – Shiny_and_Chrome Nov 18 '16 at 15:17

1. P→Q     premise


text:
# Using fetch in Firebase Functions in TypeScript

Yesterday I needed to make some kind of proxy for my project. Basically, I needed to make an endpoint that makes a GET request to another server, and return the result.

I had heard of Firebase Functions and decided to write it in that. The meat of the code should look somewhat like this:

const requestHandler = async (request, response) => {
const result = await fetch(
"https://some-service.com/.../geocode?query=" + requestQueryParam,
{
[some API keys]
},
}
);
response.send(await result.text());
};

Let's get started by reading the documentation. The entry-point is here: https://firebase.google.com/docs/functions. They document how to set up the project and make a basic function that returns "Hello world". They also give a repository that contains many examples: https://github.com/firebase/functions-samples.

However, none of those examples demonstrate how to do a fetch. They all use some npm package that provides some API.

# fetch is not defined

fetch is really nice. See the API here. I try using it, run it locally with npm run serve, open the end-point and get this runtime error:

functions: ReferenceError: fetch is not defined
at /Users/anhtuan/git/cargo/functions/lib/index.js:11:20
at cloudFunction (/Users/anhtuan/git/cargo/functions/node_modules/firebase-functions/lib/v1/providers/https.js:51:16)
at /Users/anhtuan/.nvm/versions/node/v16.17.0/lib/node_modules/firebase-tools/lib/emulator/functionsEmulatorRuntime.js:532:16
at runFunction (/Users/anhtuan/.nvm/versions/node/v16.17.0/lib/node_modules/firebase-tools/lib/emulator/functionsEmulatorRuntime.js:506:15)
at runHTTPS (/Users/anhtuan/.nvm/versions/node/v16.17.0/lib/node_modules/firebase-tools/lib/emulator/functionsEmulatorRuntime.js:531:11)
at /Users/anhtuan/.nvm/versions/node/v16.17.0/lib/node_modules/firebase-tools/lib/emulator/functionsEmulatorRuntime.js:690:27
at Layer.handle [as handle_request] (/Users/anhtuan/.nvm/versions/node/v16.17.0/lib/node_modules/firebase-tools/node_modules/express/lib/router/layer.js:95:5)

# request

Googling how to make a GET request on Firebase functions will return very few results. One of which was telling the reader to use the request package. However, that package is has been deprecated for 3 years.

The author also published a lengthy post explaining their decision. Surprisingly, this package is still being downloaded 18m times a week.

In this thread, I found another post that lists out alternatives. There are many to choose from, but who knows what might work with Firebase Functions?

# node-fetch? request-promise?

Some posts like this one mention node-fetch and some other npm packages. Apparently, one could have used request-promise but it was deprecated some time before May 2020. They recommend axios but I've never heard of it. As for node-fetch, it seems to not work either.

Even the documentation in Google Functions, which is what Firebase Functions depends on, shows an example with node-fetch, which does not actually work anymore:

Still, I tried using node-fetch. I ran npm i node-fetch --save and imported it.

import * as functions from "firebase-functions";
import fetch from "node-fetch";

When I ran the server, it said:

Failed to load function definition from source: FirebaseError: Failed to load function definition from source: Failed to generate manifest from function source: Error [ERR_REQUIRE_ESM]: require() of ES Module /Users/anhtuan/git/cargo/functions/node_modules/node-fetch/src/index.js from /Users/anhtuan/git/cargo/functions/lib/index.js not supported.
Instead change the require of /Users/anhtuan/git/cargo/functions/node_modules/node-fetch/src/index.js in /Users/anhtuan/git/cargo/functions/lib/index.js to a dynamic import() which is available in all CommonJS modules.

Which is the same as what a user reported in this StackOverflow post. One workaround apparently is to use an old version of node-fetch. As of writing, the major version number is 3, but they recommend using 2. That does not sound like a good idea at all. But hey I'm desperate, so I try it.

I change the dependency to "node-fetch": "^2.0.0" in package.json, run npm update and try running the function locally.

Now my import fetch from "node-fetch"; statement is broken:

src/index.ts:2:19 - error TS7016: Could not find a declaration file for module 'node-fetch'. '/Users/anhtuan/git/cargo/functions/node_modules/node-fetch/lib/index.js' implicitly has an 'any' type.
Try npm i --save-dev @types/node-fetch if it exists or add a new declaration (.d.ts) file containing declare module 'node-fetch';

I change it to const fetch = require("node-fetch"); and it now compiles. I run it locally with npm run serve, and the end-point actually works!

So I try to deploy it: npm run deploy. Now I get this error:

/Users/anhtuan/git/cargo/functions/src/index.ts
2:15  error  Require statement not part of import statement  @typescript-eslint/no-var-requires
✖ 1 problem (1 error, 0 warnings)

So I am guessing they are not happy with require statements and I have to use import instead.

# https Node module

I guess I should have realized from the start. fetch is implemented in Web browsers, but in Node.js, one has to use the Node.js modules such as http or https. Let's take a look at the http documentation:

I guess if you remove most of the boilerplate, this is not too bad. However, I hate that I have to add a listener on the result to listen to data and end events and collect each chunk myself.

The res object passed in the callback is of type IncomingMessage (see doc). It states that IncomingMessage implements the stream.Readable interface.

## Importing the IncomingMessage type

So at this point my code looks like this:

const https = require("node:https");

export const geocode = functions.https.onRequest(async (request, response) => {
const options = {
[...]
},
};
https.get(
url,
options,
(res) => {
[do something with the response]
}
);
});

And the line that defines the callback throws this error:

Parameter 'res' implicitly has an 'any' type.

I guess it wants me to specify the type of res. Well, I know it's an http.IncomingMessage, so let's import that and set the type:

const http = require("node:http");
const https = require("node:https");

export const geocode = functions.https.onRequest(async (request, response) => {
const options = {
[...]
},
};
https.get(
url,
options,
(res: http.IncomingMessage) => {
[do something with the response]
}
);
});

And it throws 2 errors:

• At the first line, it tells me
'http' is declared but its value is never read.
• At the callback definition, it tells me
Cannot find namespace 'http'.

Well, I am trying to declare http and use it down there. I imported http just the same as I imported https. What's wrong with my code?

It turns out changing the import to import * as http from "node:http"; fixed it. I am so rusty with all the different ways to set up and require modules and imports. Eventually I probably should brush up on them. See the MDN doc.

## Streaming the result

Back to the Firebase Functions doc: the res object is of type Response as defined in ExpressJS, which itself is a subclass of Node.js's Response class:

The res object is an enhanced version of Node’s own response object and supports all built-in fields and methods.

On Node.js's documentation, I learn that http.ServerResponse extends http.OutgoingMessage and that OutgoingMessage extends Stream.

That means that since both https.get's response and Firebase Functions's response are streams, I do not have to listen to "data" and "end" and concatenate everything, then call res.send.

My call back looks like this:

(res: http.IncomingMessage) => {
res.pipe(response);
}

And it seems to work, except for some encoding issue:

# Fixing the encoding

To finish I had to fix the encoding. It could either have been due to the server I am calling not returning the result in the right encoding, or my own function returning it in the wrong encoding, or my own function returning it in the right encoding but Chrome displaying it in the wrong encoding. After a few tries, I ended up finding that if I set the response's Content-Type, it works.

(res: http.IncomingMessage) => {
res.pipe(response);
}

# Fixing the last import

Even though it works locally, npm run deploy fails with this error:

Require statement not part of import statement  @typescript-eslint/no-var-requires

because of how I imported https. I cannot use require and should use the standard import statement.

So here's the final version of the code.

import * as functions from "firebase-functions";
import * as http from "node:http";
import * as https from "node:https";

export const geocode = functions.https.onRequest(async (request, response) => {
const options = {
[...]
},
};
https.get(
"https://some-endpoint/geocode?query=" +
encodeURI(request.query.query + ""),
options,
(res: http.IncomingMessage) => {
});


text:
# Math Help - sum of cosines

1. ## sum of cosines

I have the function: y(t) = (cos(300πt) + sin(500πt))^3

I need too expand the expression of y to get a sum of cosines with positive frequencies. Using
trigonometric identities find the frequencies of resulting sine waves.Can someone help me with that?
Thank you

2. Originally Posted by qwerty321
I have the function: y(t) = (cos(300πt) + sin(500πt))^3

I need too expand the expression of y to get a sum of cosines with positive frequencies. Using
trigonometric identities find the frequencies of resulting sine waves.Can someone help me with that?
Thank you
Why only cosine terms? Why not sine and cosine term?

3. because what I have to do is:
Expand the expression of
y(t) to get a sum of cosines with positive frequencies. Using trigonometric identities find the frequencies of resulting sine waves and compare with the frequency components obtained using MATLAB

4. ## Sum of cosines

Hello qwerty321
Originally Posted by qwerty321
Originally Posted by qwerty321
I have the function: y(t) = (cos(300πt) + sin(500πt))^3

I need too expand the expression of y to get a sum of cosines with positive frequencies. Using
trigonometric identities find the frequencies of resulting sine waves.Can someone help me with that?
Thank you

Using $A$ to stand for $300\pi t$ and $B$ for $500 \pi t$:

$(\cos A + \sin B)^3 = \cos^3A+3\cos^2A\sin B + 3\cos A \sin^2B+\sin^3B$

Now make repeated use of the following identities:

$\cos^2x = \frac{1}{2}(\cos 2x -1)$

$\sin^2x = \frac{1}{2}(1-\cos 2x)$

$\cos x \cos y = \frac{1}{2}(\cos(x+y) + \cos(x-y))$

$\sin x \cos y = \frac{1}{2}(\sin(x+y) + sin(x-y))$

So, for example: $\cos^3A = \frac{1}{2}(\cos 2A -1)\cos A$

$= \frac{1}{2}\left(\frac{1}{2}(\cos3A + \cos A) -\cos A\right)$

$= \frac{1}{4}(\cos 3A - \cos A)$

And the second term is: $3 \cos^2 A \sin B = \frac{3}{2}(\cos 2A -1) \sin B$

$= \frac{3}{2}\left(\frac{1}{2}(\sin(B+2A)+\sin(B-2A)) -\sin B \right)$

Similarly with the last two terms. Finally, if you need to get an expression in terms of cosine only, you could use $\sin x = \cos(\pi /2 - x)$.


text:
## Politics

In 1994, baseball statistics godfather Bill James developed the Keltner List, a series of 15 gut-check questions that he suggests should be asked of players who are close calls to enter the sport’s Hall of Fame. In thinking through my “call” of New Jersey, which I’ll issue later today, I realized that there are a similar set of questions that I pose to myself in the event of elections that are too close to call from the polling alone. Some of these questions are subjective, while others will require a little bit of research, but for the most part they should lend themselves to relatively clear answers.

As you look at these questions, think about how you’d answer them for New Jersey, or NY-23, or perhaps Barack Obama’s election last November, or George Bush’s in 2004. The way that I prefer to do this is to assign up to 3 points to either of the candidates (but never both) for each question, depending on the magnitude of their advantage — no points need be awarded if the factor is inapplicable or neither candidate has a discernible edge. When I do this for New Jersey, I come up with a relatively clear answer, as you’ll see later.

1. Which candidate’s supporters are more enthusiastic?

2. Which candidate is liable to have the better turnout operation?

3. Is one of the candidates a challenger to an incumbent, who might benefit from the ‘incumbent rule’?

4. Do the demographics of the undecided vote, or the weakly-attached third-party vote, favor either of the candidates?

5. Which candidate got the more favorable coverage in the morning newspaper, or on the local evening news, on the Sunday before the election?

6. Which candidate has the better ‘elevator pitch‘, particularly as encapsulated by the commercials they’re running in the 48 hours before the election?

7. Which candidate has a headwind at their back from the national political environment, or has a message that squares better with the national political mood? Which candidate’s party is liable to have the better Election Night nationwide?

8. Does either candidate begin with a built-in lead from early or absentee voting?

9. Which candidate, if any, stands to benefit from upballot or downballot races?

10. Which candidate stands to benefit from cellphone-only voters, or other voters who may not be represented in the polls?

11. Has the polling in previous elections in the state, or in similar elections in similar states, tended systematically to underestimate the performance of either candidate’s party?

12. Which candidate drew more people to their campaign appearances in the state over the last two weeks of the campaign?

13. Which candidate got more contributions from voters within the state over the last six weeks of the campaign?

14. Which candidate has run the more positive, optimistic campaign, and will leave voters feeling better about themselves as they exit the polling place?

15. Which candidate’s party controls the state’s electoral and judicial apparatus, in the event of a recount or otherwise disputed election?

Nate Silver is the founder and editor in chief of FiveThirtyEight.

Filed under , , , , ,

All Politics

### The Republican Establishment Is Waiting On The SidelinesSep 3, 2015

Never miss the best of FiveThirtyEight.


text:
# Is there a “flaw” in the backpropagation algorithm?

While trying to find a better backpropagation algorithm, I came across a paradox in my algorithm and then I found out this also happens in the usual backpropagation algorithm.

Our neural network looks like this:

In this simple example, we have no biases. The activiation function is the usual $f(x)=\frac{1}{1+e^{-x}}$

Our training set is just one datapoint: input = 0.9 and target_output = 0.9. The learning factor is set to 0.1.

The paradox happens when w2 is randomly initialized to a negative value. First, let's take a look at the "normal" situation (where the paradox does not happen). Let's say w1 and w2 are both positive, but the output is less than 0.9. w1 and w2 are both initialized at 0.1. Then to reduce the error, both w1 and w2 are increased, so the the output will get closer to 0.9. This is visible in the next graph (x is the training iteration, each training iteration contains one backpropagation).

Now let's take a look at the situation that w1 is intialized at 0.1 and w2 is initialized with a negative value (-0.5). Initially, an increase in w1 would cause a more negative value for the output layer, which increases the error. However, that's only the case because w2 is negative. Although w1 will decrease in the beginning, it will start increasing as soon as w2 becomes positive. The blue line (w1) is clearly decreasing in the beginning in the below graph from my experiment:

This "wrong" learning in the beginning of the blue line w1, is a consequence of using the derivative of the error function to induce small learning steps. Would it be better to somehow anticipate a positive w2 that will be needed anyway and so increase w1 from the beginning instead? Can we make a better backpropagation algorithm?


text:
# Calculate 67−1 (mod 119) and use this to calculate 43/67 (mod 119). Euclidean GCD algorithm

Hello I am wondering if any one can help me I am trying to figure out how to

Calculate 67−1 (mod 119) and use this to calculate 43/67 (mod 119).

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? I know I need to use the extended Euclidean GCD algorithm but don't know how

119 = 67 + 52
67 = 52 + 15
52 = (3 × 15) + 7
15 = (2 × 7) + 1

52 = 119 − 67
15 = 67 − 52 = 67 − 119 + 67 = (2 × 67) − 119
7 = 52 − (3 × 15) = 119 − 67 − (6 × 67) + (3 × 119) = (4 × 119) − (7 × 67)
1 = 15 − (2 × 7) = (2 × 67) − 119 − (8 × 119) + (14 × 67) = (16 × 67) − (9 × 119)

I cant figure out how to get passed this pont

I think you meant $67^{-1} \mod 119$. If we denote the inverse of $67 \mod 119$ by $a$, then by definition we wish to find $a$ such that $67\cdot a\equiv 1 \mod 119$, or, find an integer solution $(a,n)$ to $67a+119x=1$. We will first find the GCD of $67$ and $119$ by Euclid's algorithm. \begin{align} 119&=67\cdot 1+52\\ 67&=52\cdot 1+15\\ 52&=15\cdot 3+7\\ 15&=7\cdot 2+1\\ 7&=1\cdot 7+0 \end{align} Now we can retrace our steps to find the solution to $67a+119x=1$. We write $1=15-7\cdot 2$ (from the fourth line). By substituting $7=52-15\cdot 3$ (from the third line), we obtain $1=15-(52-15\cdot 3)\cdot 2=15\cdot 7-52\cdot 2$. Substituting again, this time $15=67-52\cdot 1$ (from the second line), we get $1=(67-52\cdot 1)\cdot 7-52\cdot 2=67\cdot 7-52\cdot 9$. Substituting the last time, $52=199-67\cdot 1$ (from the first line), we finally get $1=67\cdot 7-(119-67\cdot 1)\cdot 9=67\cdot 16-119\cdot 9$. We find the solution $(a,x)$ is $(16,-9)$, and so $a=16$, making $67^{-1}\equiv 16\mod 119$. To now get $43/67\mod 119$, we just need to multiply by $43$; we see $43/67\equiv 43\cdot 16\equiv 688\equiv 93\mod 119$.

Hope this helped!

I suppose you mean $67^{+1}\mod 119$. You only have to find a Bézout's relation between $67$ and $119$: $$u\cdot 67+v\cdot 119=1.$$ The inverse is $u\bmod119$. You can get $u$ and $v$ with the extended Euclidean algorithm.


text:
# Calculus: Derivatives I

## Constructing the Derivative

Motivation: How fast is a function changing? If the function is very steep, one would imagine the rate would be fairly high, and if the function is gradual or even flat, one would imagine the rate would be fairly low. How would one go about translating this concept into mathematics?

Secant Lines: A fine idea is to pick two points on the graph and draw a line through them. The slope of the line will show the average rate the function changes from one point to the next, as seen in Figure 1. The term for this kind of line between two points on a graph is called a secant line.

But there's a problem - it's not exact. The function is clearly steeper than the line in some region and less so in others. Furthermore, it's not clear which part of the function the line is trying to estimate: The first point? The second? The middle? Something else? In fact, one could easily pick two points that give a line that any reasonable person would agree is not very helpful. For example, Figure 2 shows that the line will be flat if the two points selected are $(0,0)$ and $(\pi,0)$.

How to improve? Well, why not make the points closer together? The closer the points are, the more accurate the estimate should be. Figure 3 is definitely more accurate than the previous two figures.

But this is math, you cry out, math is precise! Math is elegant! Is there nothing beyond this wasteland of approximations? Am I supposed to be satisfied with "just use very small differences" as the cruel failure of an answer to my thirst for precision?

In the name of the figs, no! The solution is to take the limit as the difference between the two points goes to $0$. That, young Newtonwalker, is the precise construction of a derivative.

Taking the limit: The slope between any two points $(x_0,y(x_0))$ and $(x_1,y(x_1))$ is given by the familiar formula of $\dfrac{\text{rise}}{\text{run}}$. A perk of doing harder math is that you get sexier notation, so instead we're going to denote rise, the change in $y$, as $\Delta y$, and run, the change in $x$, as $\Delta x$. The triangle symbol is the Greek letter capital delta, and means change. The expression the slope between two points is then given by:

$$\dfrac{\Delta y}{\Delta x} = \dfrac{y(x_1) - y(x_0)}{x_1 - x_0}$$

Because we're interested in the difference between the two points, rather than the two points themselves, we can make a new variable $h$ to denote this difference:

$$h = x_1 - x_0$$

Fixing up our original equation gives us the following:

$$\dfrac{\Delta y}{\Delta x} = \dfrac{y(x_0 + h) - y(x_0)}{h}$$

And now like the Eagles, we take it to the limit (although we're going to be doing this a lot more than one more time). Further, you now get even sexier notation: Capital delta usually refers to discrete changes, so to reflect the infinitesimal change, we use lowercase $d$ instead. Voilá, we have the definition of the derivative:

$$\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0}\dfrac{y(x_0 + h) - y(x_0)}{h}$$

Figure 4 below shows the derivative as the slope of the tangent line at a particular point:

The derivative is itself a function. Plugging a value into the derivative, say $x=0$, produces a value, say $\dfrac{dy}{dx}(0)=1$, that is the slope of the tangent line to the original function when $x=0$.

What the derivative is not: As defined, the derivative of a function gives the slope of the tangent line at a given point. This bears repeating - the derivative of a function gives the slope of the tangent line at a given point. It is itself a new function that is distinct from the function of which it is the derivative. The number of ways new calculus students can get confused on this point is truly impressive. It is worth listing a few of the things a derivative is not:

• The original function
• Necessarily a line
• Necessarily positive if the original function is positive
• Necessarily negative if the original function is negative
• Somehow the equation for a line that is magically tangent to the function everywhere.
• Something other than the slope of the tangent line at a given point.

Note on notation: The notation $\dfrac{dy}{dx}$ is used when differentiating a function written as $y = \ldots$, and is referred to as Leibniz notation, after Newton's contemporary who independently discovered the field of calculus but for some reason gets less credit. The notation $f'(x)$ is also used to show the derivative of $f(x) = \ldots$, where the tick mark denotes that it's a derivative.

Solving limits for general classes of functions: You may have acquired a creeping sense of unease upon learning about how to take derivatives. This process looks tedious! Must we do all this limit work every time we take a derivative? Thankfully, no! The trick is to solve for general classes of functions, and then use the resulting general forms of the derivatives to solve specific derivatives. The problems below are based on deriving these general rules, and the other topics in this section are devoted to practicing the use of these rules.

## Problems

1. Linearity of Differentiation: In layman's terms, an operator is like a function that maps functions to other functions, rather than mapping numbers to other numbers. That is to say, functions eat numbers and poop out numbers, and operators eat functions and poop out functions. The differentiation operator $D$ can be written as follows:

$$D(f) = \lim\limits_{h \rightarrow 0}\dfrac{f(x+h) - f(x)}{h}$$

A linear operator is an operator $L$ that has the following properties:

1. Constant scaling: For a constant $c$, $D(cf) = cD(f)$
2. Additivity: $D(f + g) = D(f) + D(g)$

Prove that differentiation is a linear operator.

Hint: Recall the properties of limits

1. $\lim\limits_{h \rightarrow 0} D(cf) = \lim\limits_{h \rightarrow 0} \dfrac{cf(x + h) - cf(x)}{h} \\ \lim\limits_{h \rightarrow 0} D(cf) = \lim\limits_{h \rightarrow 0} c\dfrac{f(x + h) - f(x)}{h} \\ \lim\limits_{h \rightarrow 0} D(cf) = c\lim\limits_{h \rightarrow 0} \dfrac{f(x + h) - f(x)}{h} \\ \lim\limits_{h \rightarrow 0} D(cf) = cD(f) \\$
2. $\lim\limits_{h \rightarrow 0} D(f) + D(g) = \left( \lim\limits_{h \rightarrow 0} \dfrac{f(x + h) - f(x)}{h} \right) + \left( \lim\limits_{h \rightarrow 0} \dfrac{g(x + h) - g(x)}{h} \right) \\ \lim\limits_{h \rightarrow 0} D(f) + D(g) = \lim\limits_{h \rightarrow 0} \dfrac{f(x + h) - f(x)}{h} + \dfrac{g(x + h) - g(x)}{h} \\ \lim\limits_{h \rightarrow 0} D(f) + D(g) = \lim\limits_{h \rightarrow 0} \dfrac{f(x + h) + g(x + h) - f(x) - g(x)}{h} \\ \lim\limits_{h \rightarrow 0} D(f) + D(g) = D(f+g) \\$
2. Polynomials: Compute the derivative for each of the following:

1. $y = x$
2. $y = x^2$
3. $y = x^3$

Show for the general case that for $y = x^a$, $\dfrac{dy}{dx} = ax^{a-1}$.

Hint: Remember the binomial coefficient.

1. $\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{(x+h) - x}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{h}{h} \\ \dfrac{dy}{dx} = 1 \\$
2. $\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{(x+h)^2 - x^2}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{x^2 + 2xh + h^2 - x^2}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{2xh + h^2}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} 2x + h \\ \dfrac{dy}{dx} = 2x \\$
3. $\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{(x+h)^3 - x^3}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{x^3 + 3x^2h + 3xh^2 + h^3 - x^3}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{3x^2h + 3xh^2 + h^3}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} 3x^2 + 3xh + h^2 \\ \dfrac{dy}{dx} = 3x^2 \\$
4. $\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{(x+h)^a - x^a}{h}$

The trick here is to know that $(x+h)^2 = \displaystyle\sum\limits_{i=0}^{n} \binom{n}{i}x^{n-i}h^i$:

$\dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{\left( \sum\limits_{i=0}^{n} \binom{a}{i}x^{n-i}h^i \right) - x^a}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{\left( x^a + \sum\limits_{i=1}^{a} \binom{a}{i}x^{a-i}h^i \right) - x^a}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \dfrac{\sum\limits_{i=1}^{a} \binom{a}{i}x^{a-i}h^i}{h} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \displaystyle\sum\limits_{i=1}^{a} \binom{a}{i}x^{a-i}h^{i-1} \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \left[ \binom{a}{1}x^{a-1}h^{1-1} + \displaystyle\sum\limits_{i=2}^{a} \binom{a}{i}x^{a-i}h^{i-1}\right] \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \left[ ax^{a-1}h^0 + \displaystyle\sum\limits_{i=2}^{a} \binom{a}{i}x^{a-i}h^{i-1}\right] \\ \dfrac{dy}{dx} = \lim\limits_{h \rightarrow 0} \left[ ax^{a-1} + \displaystyle\sum\limits_{i=2}^{a} \binom{a}{i}x^{a-i}h^{i-1} \right]\\ \dfrac{dy}{dx} = ax^{a-1} + \displaystyle\sum\limits_{i=2}^{a} \binom{a}{i}x^{a-i}(0)^{i-1} \\ \dfrac{dy}{dx} = ax^{a-1} + \displaystyle\sum\limits_{i=2}^{a} 0 \\ \dfrac{dy}{dx} = ax^{a-1} \\$


text:
Can I automatically draw my cards from a list?

So, I've made a format to print cards out (Shown below). Is it possible for me to fill each card environment from some sort of list, instead of having to write out \cards{foo} for each card? I could use a script to do this, but I thought it would be interesting to try it in LaTeX.

\documentclass{article}
\usepackage[margin=2cm]{geometry}

\newlength\cardheight
\newlength\cardwidth

\setlength\cardheight{0.4\textheight}
\setlength\cardwidth{0.49\textwidth}

\newcommand\cards[1]{%
\fbox{\begin{minipage}[t][\cardheight][t]{\dimexpr\cardwidth-2\fboxsep-2\fboxrule\relax}
\vspace{\baselineskip}
\huge ~ #1
\vfill
\normalsize ~ Cards Against Humanity %I should insert the CAH logo in my final version
\end{minipage}}
\hspace{1pt}}

\pagestyle{empty}

\begin{document}
\centering

\cards{%
Classicist undertones.
} %
\cards{%
A windmill full of corpses.
} %
\cards{%
A tiny horse.
} %
\cards{%
One more card.
} %

\end{document}

So, what I'd do now would be to write all the cards I want into a newline separated file, then write a quick program to wrap each line in "\cards{%\n\n}%"

Is there a way to do this all with LaTeX, so that I only have to have the one file, instead of an external card file, a conversion program and a LaTeX file?

A pure LaTeX solution (no extra package needed):

\documentclass{article}
\usepackage[margin=2cm]{geometry}

\newlength\cardheight
\newlength\cardwidth

\setlength\cardheight{0.4\textheight}
\setlength\cardwidth{0.49\textwidth}

\newcommand\card[1]{%
\fbox{\begin{minipage}[t][\cardheight][t]{\dimexpr\cardwidth-2\fboxsep-2\fboxrule\relax}
\vspace{\baselineskip}
\huge ~ #1
\vfill
\normalsize ~ Cards Against Humanity %I should insert the CAH logo in my final version
\end{minipage}}%
\hspace{1pt}}

\makeatletter
\newcommand{\cards}[1]{
\@for\@c:=#1\do{%
\card{\@c}%
}%
}
\makeatother

\pagestyle{empty}

\begin{document}
\centering

\cards{%
Classicist undertones.,%
A windmill full of corpses.,%
A tiny horse.,%
One more card.
}%

\end{document}

Here the \cards command accepts a comma separated list with the captions and loops through the list with LaTeX's \@for where in each iteration \@c will contain the current caption.

• Nice. Add a % after \end{minipage}} to avoid spurious spaces. – karlkoeller Nov 26 '13 at 14:55
• Nice. How do I escape a comma, as some of the cards have commas on them? Can I wrap them in braces like I can with etoolbox? – Canageek Nov 26 '13 at 17:21
• @Canageek yes you can: \cards{{a,b},c} will typeset two cards – Bordaigorl Nov 26 '13 at 17:49

Use any list-processing package. Here's an etoolbox version:

\documentclass{article}
\usepackage[margin=2cm]{geometry}% http://ctan.org/pkg/geometry
\usepackage{etoolbox}% http://ctan.org/pkg/etoolbox

\newlength\cardheight
\newlength\cardwidth

\setlength\cardheight{0.4\textheight}
\setlength\cardwidth{0.49\textwidth}

\newcommand{\card}[1]{%
\fbox{\begin{minipage}[t][\cardheight][t]{\dimexpr\cardwidth-2\fboxsep-2\fboxrule\relax}
\vspace{\baselineskip}
\huge ~ #1
\vfill
\normalsize ~ Cards Against Humanity %I should insert the CAH logo in my final version
\end{minipage}}%
\hspace{1pt}}
\newcommand{\cards}[1]{%
\renewcommand*{\do}[1]{\card{##1}}% How to process each item
\expandafter\docsvlist\expandafter{#1}}% Process list

\pagestyle{empty}

\begin{document}
\centering

\cards{%
Classicist undertones.,%
A windmill full of corpses.,%
A tiny horse.,%
One more card.
}%

\end{document}

The list is a comma-separated list. If an item contains a commas, then you need to wrap it in braces {..., ..}.

An equivalent LaTeX3 implementation would require the following definition of \cards:

\ExplSyntaxOn
\DeclareDocumentCommand{\cards}{ > { \SplitList { , } } m }{%
\ProcessList {#1} { \card }}% Process list
\ExplSyntaxOff


text:
# Tag Info

## Hot answers tagged cbc

15

CBC does not perform authentication This property makes it less suitable for places where authentication is required, basically any transport protocol. TLS uses CBC, but by default performs authentication over the plain text instead of the ciphertext, which opened up a host of attacks. CBC can be used here, but it is error prone and may require an ...

9

CBC mode encryption is defined as: $C_i = E_k(P_i\oplus C_{i-1})$ (with $P_i$ being the $i$th plaintext block, and $C_{i-1}, C_i$ being the ciphertext blocks. What might happen if we have a lot of ciphertext encrypted with the same key is if two ciphertexts happen to be the same, that is: $C_i = C_j$ If we see that, we can then immediately deduce that: ...

7

There are several scenarios where you wouldn’t want to use AES in CBC mode. In CBC mode, each block is dependent on a previous one. As @fgrieu nicely hinted at in his comment, using CBC means that if you have a large, encrypted file and you only want to update/change/modify a tiny fraction of it, you would have to follow the decrypt-modify-encrypt path each ...

5

With CBC mode the initialization vector is referred to as IV, because it is not nonce. There are ways to construct nonce so that it does not meet the needs of CBC mode. Random IV is one generation choice which is usually fine. Nonce can also be a counter, which is not ok here. Definitions Nonce means number used once. IV means initialization vector. CBC ...

5

Let me see if I have this right (and please correct me if I misunderstand; my conclusions depend on the details of this); you distribute images for your firmware device; these images are encrypted with a secret AES key (using AES in CBC mode); the device decrypts the image, and then runs that decrypted image. The sole check to make sure that the image ...

5

The reason why CBC is considered better than ECB has nothing to do with situations involving an attacker with a partial ciphertext; we always assume that any attacker has full access to the ciphertext. Instead, the problem with ECB is that it leaks information. Specifically, if you encrypt two messages which has two blocks of plaintexts in common, then ...

4

If your IV is predictable this is as (in)secure as assuming that you have a zero vector IV. And a zero vector IV allows you to perform a so-called Adaptive Chosen Plaintext Attack (ACPA). Why? Assume that you have a encryption mechanism that works in CBC mode. This means, that on the first iteration the $IV$ is XORed with your input message (which is ...

4

You should use random IV even when unique keys are used. This prevents key-collision attack where the attacker collects number of cryptograms that have been encrypted with unique keys and brute-forces for key. Using predictable IV will reduce security of your cryptosystem by a factor of N (where N is the number of ciphertexts created). The attack recovers ...

4

Normally you don't want to reverse the encryption used within a DRBG. Schemes like PKCS#7 padding and CTS are required to deterministically reverse the padding during decryption. If you just want to have a final block, you should be fine by using zero padding until the end of the block. Of course, if this zero padding is actually harming the output of your ...

4

From the sound of your questions, it almost appears that you have some confusion between the CBC-MAC key and the CBC-MAC tag. The CBC-MAC algorithm takes the message (in this case, most likely the ciphertext) and a secret key; it outputs a tag (which can be public). The security property of CBC-MAC is that someone who does not know the key cannot generate ...

4

AES-NI is just a fast way for the processor to execute the calculations of AES. Normally the computer has to calculate every single step of the AES key schedule and the rounds as a single instruction: Substitute it with the S-boxes, shift the rows, mix the columns, XOR the round key. This is called a software implementation. Every instruction has to be done ...

3

There is not much difference and in practice the terms are often used to mean the same thing. In this context however the Nonce does not have to keep to the random properties that the IV has. As explained in the paper: A probabilistic encryption scheme $C = \varepsilon^R_K (P)$ is an IV-based encryption scheme, syntactically, but we are suggesting that, ...

3

Well, if you have hardware which you can give it a long ciphertext block, and say "decrypt this block in one shot", well, one could argue that reusing the last ciphertext block as the next IV might give some minimal amount of gain; you would concatinate all the ciphertexts in order, and ask for the hardware to decrypt the entire thing -- the result will be ...

3

You should read the wikipedia article about disk encryption. In short: for disk encryption, data is organized in sectors (for instance of size 512 bytes), and data may be encrypted with a chaining mode of operation such as CBC only inside these sectors, using a different initialization vector for each sector.

3

Remark: in One Time Pad the pad is used once, thus this is not OTP, since here $k$ is reused. Hint for part 1: Write the relations between $k$, the message blocks $m_i$, the ciphertext blocks $\small C_i$ with the convention $\small\text{IV}=\small C_0$. Then, find equations that allow computing the desired $m_3⊕m_4$ from known quantities. Hint for part 2, ...

3

First of all, I suggest you to try use as IV first 16 bytes of encrypted file. Because in general IV is the first block of ciphertext. But if that doesn't work, then – of course – you can decrypt all message except first block. Just use first block as IV, and start to decrypt from second block. That will work because CBC does not provide integrity, and ...

3

To see the problem, let's see how I would chain up a single function (call it $AES\,CBC_k(iv, m)$) which only encrypts a single block at a time into something that can encrypt "chunks" of any size. Let $m=m_1||m_2||m_3||m_4$ be the message I want to encrypt. Each $m_i$ is a single block (in AES it is 128 bits). I want to use $AES\,CBC_k$ to encrypt $m$. The ...

3

Just for completeness sake, CBC is defined as follows: The error you have made is that: $$M;N = (M_1, ..., M_n, N_1 ⊕ \mathbf{T_m}, N_2, ..., N_n)$$ (I've changed notation from M||N to M;N to reflect this isn't just concatenation) You need to cancel the tag from the message $M$, not the tag from the $N$ message. In that case, $T_{M;N}=T_N$ as required.

3

The usual mode for disk encryption is XTS (let's say the mode suggested by the NIST). AEAD cipher seems to be promissing but typically with the GCM you will have also to store an authentication tag per encrypted block which may lead to a complex implementation (but interesting). I believe that regarding at least integrity, there exist "new" file systems ...

3

My first thought was that I could set the IV to the first 8 bytes of the CT [and] decode the rest[.] This is exactly how CBC works. For all blocks but the first, encryption is defined by $C_n=E_K(C_{n-1}\oplus P_n)$ and, therefore, decryption is achieved by $P_n=C_{n-1}\oplus D_K(C_n)$. Since there is no previous ciphertext for the first plaintext ...

3

…are any other modes of operation vulnerable to padding oracle attacks? Nope, it’s purely restricted to CBC. A padding oracle attack, also known as “Vaudenay attack” because it was originally published by Serge Vaudenay in 2002 and introduced at EUROCRYPT 2002, is an attack against cipher-block chaining. The attack works against any block cipher in ...

3

I am little curious about how do we calculate hardness proof of any cryptography algorithm? This is typically done by assuming some problem is hard (e.g., solving discrete log). Then proving that if someone can break the cryptography algorithm (e.g., diffie-hellman) that they can also break the hard problem. Once this relationship is established, we ...

3

I didn't find anything about the exact way Crashplan encrypts files, only that it uses Blowfish in CBC mode. The block size of Blowfish is 64 bit, so there are $2^{64}$ different input blocks and the same number of output blocks. All in all $147573953$ terabytes of different output data. The problem with this is the birthday attack. Summarized it says that ...

3

AES CBC usually requires padding, such as PKCS#7 padding. This padding is 1 to 16 bytes, 16 being the block size of AES. The HMAC will add 256 / 8 = 32 bytes to the total. Usually you will need to store the randomized IV as well with ciphertext, to allow for reuse of the key, adding another 16 bytes (the block size again). So the total overhead will be about ...

3

Rejecting replays is the duty of a higher level protocol. Simple authenticated encryption will accept any message with a valid MAC, even if you receive it several times. Decryption is a stateless process, but you need state to keep track of messages you already received. For example you could associate an increasing counter for each message you send. The ...

2

In the padding oracle attack you have an oracle that only tells you whether a particular chosen ciphertext decrypts to a correctly padded plaintext. That oracle is used to build a last word oracle, which used iteratively can reveal a whole message. The reason it works in CBC mode is that we can make predictable, arbitrary changes to the plaintext of the ...

2

Depending on how malleability is defined, the question actually has some merit. Given to the Wikipedia definition of malleability, a cipher is malleable if there exists at least one function $g$ over the set of possible cipher texts, and one function $f$ over the set of possible plain texts, such that given any cipher text $c_0$, the cipher text $c_1 = ... 2 It is insecure to reuse the$IV$with AES-CBC. At the very least, if the files have a common prefix, this will be revealed as a common prefix of the ciphertexts. For AES-CBC, the only way to ensure confidentiality is to use random$IV\$s. However, if you are not restricted to a particular CBC mode, the nonce-based Counter mode (CTR) might solve your problem. ...

2

An IV is an intial vector, which means it is an initial vector of data used when you start a chaining mode. It has no interesting properties of its own. If the IV is a nonce, that means it is a number used once (eg CTR mode). This means that (by changing the IV) we ensure that the process is never run on exactly the same input data (even if messages are ...

2

There are a couple of things going on: First of all, the DES key FF FF FF FF FF FF FF FF happens to be a "DES weak key"; by that, we mean that if you send a block through the cipher twice, it'll end up with the original value; that is: $$X = DES_{weak}( DES_{weak} ( X ))$$ You are obviously encrypting in CBC mode with a zero IV. So, let us look at what ...

Only top voted, non community-wiki answers of a minimum length are eligible