intvert.invert_1D

invert_1D(signal, known_coeffs={}, **lattice_params)

Invert an integer signal from limited DFT spectrum.

Invert the last axis of an integer signal from a limited set of sampled DFT coefficients. The sampled frequencies may be provided in known_coeffs, which should be structured like the output of select_coeffs_1D. The input signal should be given in real space, so the known DFT coefficients are obtained by calling mp_dft on signal. If no known frequencies are provided, they are chosen automatically from signal by assuming nonzero DFT coefficients are known. It is assumed that a sufficient set of coefficients are known to guarantee uniqueness of inversion.

Parameters:

  • signal (mpfr arraylike) – Sampled signal.

  • known_coeffs (dict, optional) – Dictionary of known frequencies, by default {}

Returns:

Inverted signal.

Return type:

int ndarray

Raises:

InversionError – If inversion fails for any subproblem. The current lattice parameter values are given, so they may be tuned to allow inversion.

See also

sample_1D

constructing the sampled input

select_coeffs_1D

selecting a partial set of known DFT coefficients

invert_2D

analogous 2D function

Parameters:

  • beta0 (float) – Penalty for coefficient of last lattice basis column, by default 1e-1

  • beta1 (float) – Penalty for missing linear constraints with integer coefficients, by default 1e3

  • beta2 (float) – Penalty for missing linear constraints with real coefficients, by default 1e14

  • beta3 (float) – Rescale before truncation, by default 1e2

  • delta (float) – LLL approximation parameter delta, by default 0.9972

  • epsilon (float) – Absolute tolerance for verifying shortest vectors against DFT coefficient data.

Notes

The parameters beta0, beta1, beta2, beta3, delta, and epsilon are passed as keyword arguments through **lattice_params. They control the lattice-based integer programming solver.

This dynamic programming implementation of 1D inversion iterates through the divisors \(d\) of the signal size N = len(signal). Each iteration requires solving an integer linear program in \(d\) variables. The integer program is reduced to the shortest vector problem by constructing a lattice basis with reduction parameters \(\beta_0,\beta_1,\beta_2\) [LV]. This shortest vector problem is solved with the LLL approximation algorithm [LLL] using the given value of \(\delta\). The vector returned by LLL is rejected if the known part of its DFT does not match signal to absolute tolerance epsilon, causing an InversionError.

The default values are optimized for double precision. When using increased precision for larger inversions, it may be necessary to increase beta2 and beta3 and decrease epsilon.

Examples

Sampling and inverting with automatically selected coefficients:

>>> signal = np.array([1, 1, 0, 1, 0, 1, 0])
>>> sampled = intvert.sample_1D(signal)
>>> np.allclose(signal, intvert.invert_1D(sampled))
True

Sampling and inverting with user-selected coefficients:

>>> known_coeffs = {7: {0}, 1: {2}}
>>> sampled = intvert.sample_1D(signal, known_coeffs)
>>> np.allclose(signal, intvert.invert_1D(sampled, known_coeffs))
True

Sampling with user selection and inverting with automatically selected coefficients:

>>> np.allclose(signal, intvert.invert_1D(sampled))
True

Inverting a larger example:

>>> signal = np.random.randint(0, 2, 30)
>>> signal
array([1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 0]) # random
>>> sampled = intvert.sample_1D(signal)
>>> np.allclose(signal, intvert.invert_1D(sampled))
True

With insufficient precision, inversion may fail for long signals with large integers:

>>> signal = np.arange(29)
>>> sampled = intvert.sample_1D(signal)
>>> np.allclose(signal, intvert.invert_1D(sampled))
False

In this case, increasing precision and beta2 allows inversion:

>>> with gmpy2.get_context() as c:
...     c.precision = 100
...     sampled = intvert.sample_1D(signal)
...     np.allclose(signal, intvert.invert_1D(sampled, beta2=1e20))
...
True

Or providing more DFT coefficients also allows inversion:

>>> known_coeffs = intvert.select_coeffs_1D(29, 2)
>>> sampled = intvert.sample_1D(signal, known_coeffs)
>>> np.allclose(signal, intvert.invert_1D(sampled, known_coeffs))
True