Support for graph convolution and differential operators

matthieumeo · Mar 3, 2021 · dd33222 · dd33222
1 parent 0e70a6d
commit dd33222
Show file tree

Hide file tree

Showing 25 changed files with 914 additions and 0 deletions.
diff --git a/doc/.DS_Store b/doc/.DS_Store
diff --git a/doc/api/.DS_Store b/doc/api/.DS_Store
diff --git a/doc/api/index.rst b/doc/api/index.rst
@@ -0,0 +1,8 @@
+Pycsou-gsp API
+##############
+
+.. toctree::
+   :maxdepth: 1
+   :hidden:
+
+   operators/index
diff --git a/doc/api/operators/index.rst b/doc/api/operators/index.rst
@@ -0,0 +1,11 @@
+.. _operators:
+
+Linear Operators
+================
+
+.. autosummary::
+   :toctree:
+
+   pycsou_gsp.linop.base
+   pycsou_gsp.linop.conv
+   pycsou_gsp.linop.diff
diff --git a/doc/api/operators/pycsou_gsp.linop.base.rst b/doc/api/operators/pycsou_gsp.linop.base.rst
@@ -0,0 +1,10 @@
+Polynomial Filter
+=================
+
+Base class for polynomial graph filters.
+
+.. currentmodule:: pycsou_gsp.linop.base
+   :special-members: __init__
+
+.. autosummary:: 
+   PolynomialLinearOperator
diff --git a/doc/api/operators/pycsou_gsp.linop.conv.rst b/doc/api/operators/pycsou_gsp.linop.conv.rst
@@ -0,0 +1,14 @@
+Convolution Operators
+=====================
+
+Base class for graph convolution operators. 
+
+.. automodule:: pycsou_gsp.linop.conv
+   :special-members: __init__
+
+   .. autosummary::
+
+      GraphConvolution   
+
+
+
diff --git a/doc/api/operators/pycsou_gsp.linop.diff.rst b/doc/api/operators/pycsou_gsp.linop.diff.rst
@@ -0,0 +1,14 @@
+Differential Operators
+======================
+
+Base class for graph convolution operators. 
+
+.. automodule:: pycsou_gsp.linop.diff
+   :special-members: __init__
+
+   .. autosummary::   
+      GraphLaplacian
+      GraphGradient
+      GeneralisedGraphLaplacian
+
+
diff --git a/doc/conf.py b/doc/conf.py
@@ -0,0 +1,116 @@
+import configparser
+import datetime
+import pathlib
+import re
+from typing import Mapping
+
+
+def setup_config() -> configparser.ConfigParser:
+    """
+    Load information contained in `setup.cfg`.
+    """
+    sphinx_src_dir = pathlib.Path(__file__).parent
+    setup_path = sphinx_src_dir / ".." / "setup.cfg"
+    setup_path = setup_path.resolve(strict=True)
+
+    with setup_path.open(mode="r") as f:
+        cfg = configparser.ConfigParser()
+        cfg.read_file(f)
+    return cfg
+
+
+def pkg_info() -> Mapping:
+    """
+    Load information contained in `PKG-INFO`.
+    """
+    sphinx_src_dir = pathlib.Path(__file__).parent
+    info_path = sphinx_src_dir / ".." / "pycsou.egg-info" / "PKG-INFO"
+    info_path = info_path.resolve(strict=True)
+
+    # Pattern definitions
+    pat_version = r"Version: (.+)$"
+
+    with info_path.open(mode="r") as f:
+        info = dict(version=None)
+        for line in f:
+            m = re.match(pat_version, line)
+            if m is not None:
+                info["version"] = m.group(1)
+    return info
+
+
+# -- Project information -----------------------------------------------------
+cfg, info = setup_config(), pkg_info()
+project = cfg.get("metadata", "name")
+author = cfg.get("metadata", "author")
+copyright = f"{datetime.date.today().year}, {author}"
+version = release = info["version"]
+
+# -- General configuration ---------------------------------------------------
+extensions = [
+    "sphinx.ext.autodoc",
+    "sphinx.ext.autosummary",
+    "sphinx.ext.doctest",
+    "sphinx.ext.intersphinx",
+    "sphinx.ext.mathjax",
+    "sphinx.ext.napoleon",
+    "sphinx.ext.todo",
+    "sphinx.ext.viewcode",
+    "matplotlib.sphinxext.plot_directive",
+]
+
+templates_path = ["_templates"]
+master_doc = "index"
+exclude_patterns = []
+pygments_style = "sphinx"
+add_module_names = False
+plot_include_source = True
+
+# -- Options for HTML output -------------------------------------------------
+html_theme = "sphinx_rtd_theme"
+html_theme_options = {"navigation_depth": -1, "titles_only": False}
+
+# -- Options for HTMLHelp output ---------------------------------------------
+htmlhelp_basename = "Pycsou-gsp"
+html_context = {
+    'menu_links_name': 'Repository',
+    'menu_links': [
+        ('<i class="fa fa-github fa-fw"></i> Source Code', 'https://github.com/matthieumeo/pycsou-gsp'),
+        #('<i class="fa fa-users fa-fw"></i> Contributing', 'https://github.com/PyLops/pylops/blob/master/CONTRIBUTING.md'),
+    ],
+    'doc_path': 'docs/source',
+    'github_project': 'matthieumeo',
+    'github_repo': 'pycsou-gsp',
+    'github_version': 'master',
+}
+
+# -- Extension configuration -------------------------------------------------
+# -- Options for autosummary extension ---------------------------------------
+autosummary_generate = True
+
+# -- Options for autodoc extension -------------------------------------------
+autodoc_member_order = "bysource"
+autodoc_default_flags = [
+    "members",
+    # 'inherited-members',
+    "show-inheritance",
+]
+autodoc_inherit_docstrings = True
+
+# -- Options for intersphinx extension ---------------------------------------
+intersphinx_mapping = {
+    "python": ("https://docs.python.org/3", None),
+    "NumPy [latest]": ("https://docs.scipy.org/doc/numpy/", None),
+    "SciPy [latest]": ("https://docs.scipy.org/doc/scipy/reference", None),
+    "pylops [latest]": ("https://pylops.readthedocs.io/en/latest", None),
+    "dask [latest]": ("https://docs.dask.org/en/latest/", None),
+    "pandas": ("http://pandas.pydata.org/pandas-docs/stable/", None),
+    "matplotlib": ("https://matplotlib.org/", None)
+}
+
+# -- Options for napoleon extension ------------------------------------------
+napoleon_google_docstring = False
+napoleon_numpy_docstring = True
+
+# -- Options for todo extension ----------------------------------------------
+todo_include_todos = True
diff --git a/doc/general/.DS_Store b/doc/general/.DS_Store
diff --git a/doc/general/install.rst b/doc/general/install.rst
@@ -0,0 +1,60 @@
+.. _installation:
+
+Installation
+============
+
+Pycsou-gsp requires Python 3.6 or greater.It is developed and tested on x86_64 systems running MacOS and Linux.
+
+
+Dependencies
+------------
+Before installing Pycsou-gsp, make sure that the base package Pycsou is correctly installed on your machine. Installation instructions for Pycsou are available at `that link <https://matthieumeo.github.io/pycsou/html/general/install.html>`_. 
+
+The package extra dependencies are listed in the files ``requirements.txt`` and ``requirements-conda.txt``. 
+It is recommended to install those extra dependencies using `Miniconda <https://conda.io/miniconda.html>`_ or
+`Anaconda <https://www.anaconda.com/download/#linux>`_. This
+is not just a pure stylistic choice but comes with some *hidden* advantages, such as the linking to
+``Intel MKL`` library (a highly optimized BLAS library created by Intel).
+
+.. code-block:: bash
+   
+   >> conda install --channel=conda-forge --file=requirements-conda.txt
+
+
+Quick Install
+-------------
+
+Pycsou-gsp is also available on `Pypi <https://pypi.org/project/pycsou-gsp/>`_. You can hence install it very simply via the command: 
+
+.. code-block:: bash
+   
+   >> pip install pycsou-gsp
+
+If you have previously activated your conda environment ``pip`` will install Pycsou in said environment. Otherwise it will install it in your base environment together with the various dependencies obtained from the file ``requirements.txt``.
+
+
+Developper Install
+------------------
+
+It is also possible to install Pycsou-gsp from the source for developpers: 
+
+
+.. code-block:: bash
+   
+   >> git clone https://github.com/matthieumeo/pycsou-gsp
+   >> cd <repository_dir>/
+   >> pip install -e .
+
+The package documentation can be generated with: 
+
+.. code-block:: bash
+   
+   >> conda install sphinx=='2.1.*'            \
+                    sphinx_rtd_theme=='0.4.*'
+   >> python3 setup.py build_sphinx  
+
+You can verify that the installation was successful by running the package doctests: 
+
+.. code-block:: bash
+   
+   >> python3 test.py
diff --git a/doc/images/.DS_Store b/doc/images/.DS_Store
diff --git a/doc/images/pycsou.png b/doc/images/pycsou.png
diff --git a/doc/index.rst b/doc/index.rst
@@ -0,0 +1,46 @@
+.. image:: /images/pycsou.png
+  :width: 50 %
+  :align: center
+  :target: https://github.com/matthieumeo/pycsou-gsp
+
+.. image:: https://zenodo.org/badge/277582581.svg
+   :target: https://zenodo.org/badge/latestdoi/277582581
+
+
+*Pycsou-gsp* is the graph signal processing extension of the Python 3 package Pycsou for solving linear inverse problems. The extension offers implementations of graph *convolution* and *differential* operators, compatible with Pycsou's interface for linear operators. 
+
+Graphs in *Pycsou-gsp* are instances from the class ``pygsp.graphs.Graph`` from the `pygsp <https://github.com/epfl-lts2/pygsp>`_ library for graph signal processing with Python. 
+
+Content
+-------
+
+The package is organised as follows:
+
+1. The subpackage ``pycsou_gsp.linop`` implements the following common graph linear operators:
+  * Graph convolution operators: :py:class:`~pycsou_gsp.linop.conv.GraphConvolution`
+  * Graph differential operators: :py:class:`~pycsou_gsp.linop.diff.GraphLaplacian`, :py:class:`~pycsou_gsp.linop.diff.GraphGradient`, :py:class:`~pycsou_gsp.linop.diff.GeneralisedGraphLaplacian`.
+
+2. The subpackage ``pycsou_gsp.tesselation`` provides routines for generating graphs from discrete tessellations of continuous manifolds such as the sphere. 
+
+
+.. toctree::
+   :maxdepth: 1
+   :caption: Installation
+   :hidden:
+
+   general/install
+
+.. toctree::
+   :maxdepth: 2
+   :hidden:
+   :caption: Reference documentation
+
+   api/index
+
+
+.. Indices and tables
+.. ==================
+
+.. * :ref:`genindex`
+.. * :ref:`modindex`
+.. * :ref:`search`
diff --git a/pycsou_gsp/.DS_Store b/pycsou_gsp/.DS_Store
diff --git a/pycsou_gsp/__init__.py b/pycsou_gsp/__init__.py
diff --git a/pycsou_gsp/linop/__init__.py b/pycsou_gsp/linop/__init__.py
@@ -0,0 +1 @@
+from pycsou_gsp.linop import *
diff --git a/pycsou_gsp/linop/base.py b/pycsou_gsp/linop/base.py
@@ -0,0 +1,89 @@
+# #############################################################################
+# base.py
+# =======
+# Author : Matthieu Simeoni [matthieu.simeoni@gmail.com]
+# #############################################################################
+
+r"""
+Base class for polynomial graph operators. Useful for implementing graph convolutions and generalised graph differential operators.
+"""
+from numbers import Number
+from typing import Union
+
+import numpy as np
+
+from pycsou.core.linop import LinearOperator
+
+
+class PolynomialLinearOperator(LinearOperator):
+    r"""
+    Polynomial linear operator :math:`P(L)`.
+
+    Given a polynomial :math:`P(x)=\sum_{k=0}^N a_k x^k` and a square linear operator :math:`\mathbf{L}:\mathbb{R}^N\to \mathbb{R}^N,`
+    we define the polynomial linear operator :math:`P(\mathbf{L}):\mathbb{R}^N\to \mathbb{R}^N` as:
+
+    .. math::
+
+       P(\mathbf{L})=\sum_{k=0}^N a_k \mathbf{L}^k,
+
+    where :math:`\mathbf{L}^0` is the identity matrix.
+    The *adjoint* of :math:`P(\mathbf{L})` is given by:
+
+    .. math::
+
+       P(\mathbf{L})^\ast=\sum_{k=0}^N a_k (\mathbf{L}^\ast)^k.
+
+    Examples
+    --------
+
+    .. doctests::
+
+       >>> from pycsou.linop import DenseLinearOperator
+       >>> from pycsou_gsp.linop.base import PolynomialLinearOperator
+       >>> L = DenseLinearOperator(np.arange(16).reshape(8,8))
+       >>> PL = PolynomialLinearOperator(LinOp=L, coeffs=[1/2 ,2, 1])
+       >>> x = np.arange(8)
+       >>> np.allclose(PL(x), x/2 + 2 * L(x) + (L**2)(x))
+       True
+
+    """
+
+    def __init__(self, LinOp: LinearOperator, coeffs: Union[np.ndarray, list, tuple]):
+        r"""
+
+        Parameters
+        ----------
+        LinOp: pycsou.core.LinearOperator
+            Square linear operator :math:`\mathbf{L}`.
+        coeffs: Union[np.ndarray, list, tuple]
+            Coefficients :math:`\{a_0,\ldots, a_N\}` of the polynomial :math:`P`.
+        """
+        self.coeffs = np.asarray(coeffs).astype(LinOp.dtype)
+        if LinOp.shape[0] != LinOp.shape[1]:
+            raise ValueError('Input linear operator must be square.')
+        else:
+            self.Linop = LinOp
+        super(PolynomialLinearOperator, self).__init__(shape=LinOp.shape, dtype=LinOp.dtype,
+                                                       is_explicit=LinOp.is_explicit, is_dense=LinOp.is_dense,
+                                                       is_sparse=LinOp.is_sparse,
+                                                       is_dask=LinOp.is_dask,
+                                                       is_symmetric=LinOp.is_symmetric)
+
+    def __call__(self, x: Union[Number, np.ndarray]) -> Union[Number, np.ndarray]:
+        z = x.astype(self.dtype)
+        y = self.coeffs[0] * x
+        for i in range(1, len(self.coeffs)):
+            z = self.Linop(z)
+            y += self.coeffs[i] * z
+        return y
+
+    def adjoint(self, x: Union[Number, np.ndarray]) -> Union[Number, np.ndarray]:
+        if self.is_symmetric:
+            return self(x)
+        else:
+            z = x.astype(self.dtype)
+            y = np.conj(self.coeffs[0]) * x
+            for i in range(1, len(self.coeffs)):
+                z = self.Linop.adjoint(z)
+                y += np.conj(self.coeffs[i]) * z
+            return y