<commit_before># -*- coding: utf-8 -*-

# Copyright 2018 <NAME>, <NAME>
#     https://www.tu-ilmenau.de/it-ems/
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import numpy as np
cimport numpy as np
import numpy.linalg as npl

from ..core.types cimport *
from ..Matrix cimport Matrix
from .Algorithm cimport Algorithm


cdef class OMP(Algorithm):
    r"""Orthogonal Matching Pursuit

    **Definition and Interface**:
    For a given matrix :math:`A \in \mathbb{C}^{m \times N}` with
    :math:`m \ll N` and a vector :math:`b \in \mathbb{C}^m` we approximately
    solve

    .. math::
        \min\limits_{ x \in \mathbb{C}^N} \Vert x \Vert_0
        \quad\mathrm{s.t.}\quad A \cdot x =  x.

    If it holds that :math:`b =  A \cdot  x_0` for some :math:`k`-sparse
    :math:`x_0` and :math:`k` is low enough, we can recover :math:`x_0` via
    OMP [1]_.

    This type of problem as the one described above occurs in Compressed
    Sensing and Sparse Signal Recovery, where signals are approximated by
    sparse representations.

    >>> # import the packages
    >>> import numpy.linalg as npl
    >>> import numpy as np
    >>> import fastmat as fm
    >>> import fastmat.algorithms as fma
    >>> # define the dimensions
    >>> # and the sparsity
    >>> n, k = 512, 3
    >>> # define the sampling positions
    >>> t = np.linspace(0, 20 * np.pi, n)
    >>> # construct the convolution matrix
    >>> c = np.cos(2 * t) * np.exp(-t ** 2)
    >>> C = fm.Circulant(c)
    >>> # create the ground truth
    >>> x = np.zeros(n)
    >>> x[npr.choice(range(n), k, replace=0)] = 1
    >>> b = C * x
    >>> # reconstruct it
    >>> omp = fma.OMP(C, numMaxSteps=100)
    >>> y = omp.process(b)
    >>> # test if they are close in the
    >>> # domain of C
    >>> print(npl.norm(C * y - b))

    We describe a sparse deconvolution problem, where the signal is in
    :math:`\mathbb{R}^{512}` and consists of :math:`3` windowed cosine pulses
    of the form :math:`c` with circulant displacement. Then we take the
    convolution and try to recover the location of the pulses using the OMP
    algorithm.

    .. note::
     The algorithm exploits two mathematical shortcuts. First it obviously
     uses the fast transform of the involved system matrix during the
     correlation step and second it uses a method to calculate the pseudo
     inverse after a rank-:math:`1` update of the matrix.

    .. todo::
      - optimize einsum-stuff

    .. [1]  <NAME>, <NAME>, "Matching pursuits with time-frequency
             dictionaries", IEEE Transactions on Signal Processing, vol. 41,
             no. 12, pp. 3397-3415, Dec 1993

    Parameters
    ----------
    fmatA : fm.Matrix
        the system matrix
    arrB : np.ndarray
        the measurement vector
    numMaxSteps : int
        the desired sparsity order

    Returns
    -------
    np.ndarray
        solution array
    """

    def __init__(self, fmatA, **kwargs):

        # check the must-have parameters
        if not isinstance(fmatA, Matrix):
            raise TypeError("fmatA must be a fastmat matrix")
        self.fmatA = fmatA

        # set default parameters (and create attributes)
        self.numMaxSteps = 0

        # initialize callbacks
        self.cbStep = None

        # Update with extra arguments
        self.updateParameters(**kwargs)

    cpdef np.ndarray _process(self, np.ndarray arrB):
        #     fmatA           - input system matrix
        #     arrB            - input data vector (measurements)
        #     numMaxSteps            - specified sparsity order, i.e. number of
        #                       iterations to run
        #     numN,numM       - number of rows / columns of the system matrix
        #     numL            - number of problems to solve
        #     arrDiag         - array that contains column norms of fmatA
        #     numStrideSize   - size of strides during norm calculation
        #     numStrides      - number of whole strides to go through
        #     numPreSteps     - number of entries that do not fit in whole
        #                       strides
        #

        if arrB.ndim > 2:
            raise ValueError("Only n x m arrays are supported for OMP")

        if arrB.ndim == 1:
            self.arrB = arrB.reshape((-1, 1))
        else:
            self.arrB = arrB<commit_msg>Disallow zero-dim arrays in OMP<commit_after># -*- coding: utf-8 -*-

# Copyright 2018 <NAME>, <NAME>
#     https://www.tu-ilmenau.de/it-ems/
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import numpy as np
cimport numpy as np
import numpy.linalg as npl

from ..core.types cimport *
from ..Matrix cimport Matrix
from .Algorithm cimport Algorithm


cdef class OMP(Algorithm):
    r"""Orthogonal Matching Pursuit

    **Definition and Interface**:
    For a given matrix :math:`A \in \mathbb{C}^{m \times N}` with
    :math:`m \ll N` and a vector :math:`b \in \mathbb{C}^m` we approximately
    solve

    .. math::
        \min\limits_{ x \in \mathbb{C}^N} \Vert x \Vert_0
        \quad\mathrm{s.t.}\quad A \cdot x =  x.

    If it holds that :math:`b =  A \cdot  x_0` for some :math:`k`-sparse
    :math:`x_0` and :math:`k` is low enough, we can recover :math:`x_0` via
    OMP [1]_.

    This type of problem as the one described above occurs in Compressed
    Sensing and Sparse Signal Recovery, where signals are approximated by
    sparse representations.

    >>> # import the packages
    >>> import numpy.linalg as npl
    >>> import numpy as np
    >>> import fastmat as fm
    >>> import fastmat.algorithms as fma
    >>> # define the dimensions
    >>> # and the sparsity
    >>> n, k = 512, 3
    >>> # define the sampling positions
    >>> t = np.linspace(0, 20 * np.pi, n)
    >>> # construct the convolution matrix
    >>> c = np.cos(2 * t)
    >>> C = fm.Circulant(c)
    >>> # create the ground truth
    >>> x = np.zeros(n)
    >>> x[npr.choice(range(n), k, replace=0)] = 1
    >>> b = C * x
    >>> # reconstruct it
    >>> omp = fma.OMP(C, numMaxSteps=100)
    >>> y = omp.process(b)
    >>> # test if they are close in the
    >>> # domain of C
    >>> print(npl.norm(C * y - b))

    We describe a sparse deconvolution problem, where the signal is in
    :math:`\mathbb{R}^{512}` and consists of :math:`3` windowed cosine pulses
    of the form :math:`c` with circulant displacement. Then we take the
    convolution and try to recover the location of the pulses using the OMP
    algorithm.

    .. note::
     The algorithm exploits two mathematical shortcuts. First it obviously
     uses the fast transform of the involved system matrix during the
     correlation step and second it uses a method to calculate the pseudo
     inverse after a rank-:math:`1` update of the matrix.

    .. todo::
      - optimize einsum-stuff

    .. [1]  <NAME>, <NAME>, "Matching pursuits with time-frequency
             dictionaries", IEEE Transactions on Signal Processing, vol. 41,
             no. 12, pp. 3397-3415, Dec 1993

    Parameters
    ----------
    fmatA : fm.Matrix
        the system matrix
    arrB : np.ndarray
        the measurement vector
    numMaxSteps : int
        the desired sparsity order

    Returns
    -------
    np.ndarray
        solution array
    """

    def __init__(self, fmatA, **kwargs):

        # check the must-have parameters
        if not isinstance(fmatA, Matrix):
            raise TypeError("fmatA must be a fastmat matrix")
        self.fmatA = fmatA

        # set default parameters (and create attributes)
        self.numMaxSteps = 0

        # initialize callbacks
        self.cbStep = None

        # Update with extra arguments
        self.updateParameters(**kwargs)

    cpdef np.ndarray _process(self, np.ndarray arrB):
        #     fmatA           - input system matrix
        #     arrB            - input data vector (measurements)
        #     numMaxSteps            - specified sparsity order, i.e. number of
        #                       iterations to run
        #     numN,numM       - number of rows / columns of the system matrix
        #     numL            - number of problems to solve
        #     arrDiag         - array that contains column norms of fmatA
        #     numStrideSize   - size of strides during norm calculation
        #     numStrides      - number of whole strides to go through
        #     numPreSteps     - number of entries that do not fit in whole
        #                       strides
        #

        if arrB.ndim > 2 or arrB.ndim < 1:
            raise ValueError("Only n x m arrays are supported for OMP")

        if arrB.ndim == 1:
            self.arrB = arrB.reshape((-1, 1))
        else:
            self.arrB = arrB

        if self.numMaxSteps <= 0:
            raise ValueError("OMP would like to do at least one step for you")
{'fraction_non_alphanumeric': 0.09831718510963794, 'fraction_numerical': 0.011320754716981131, 'mean_word_length': 2.158132045088567, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 151, 'https://': 2, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3797916', 'n_tokens_mistral': 2960, 'n_tokens_neox': 2796, 'n_words': 1111}