Previous Up Next

7  Miscellaneous Functions

7.1  Function spams.conjGrad

Implementation of a conjugate gradient for solving a linear system Ax=b when A is positive definite. In some cases, it is faster than the Matlab function pcg, especially when the library uses the Intel Math Kernel Library.

#
# Name: conjGrad
#
# Usage: spams.conjGrad(A,b,x0 = None,tol = 1e-10,itermax = None)
#
# Description:
#     Conjugate gradient algorithm, sometimes faster than the 
#    equivalent python function solve. In order to solve Ax=b;
#
# Inputs:
#       A:  double square n x n matrix. HAS TO BE POSITIVE DEFINITE
#       b:  double vector of length n.
#       x0: double vector of length n. (optional) initial guess.
#       tol: (optional) tolerance.
#       itermax: (optional) maximum number of iterations.
#
# Output:
#       x: double vector of length n.
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
A = np.asfortranarray(np.random.normal(size = (5000,500)))
A = np.asfortranarray(np.dot(A.T,A),dtype=myfloat)
b = np.ones((A.shape[1],),dtype=myfloat,order="FORTRAN")
x0 = b
tol = 1e-4
itermax = int(0.5 * len(b))

tic = time.time()
for i in xrange(0,20):
    y1 = np.linalg.solve(A,b)
tac = time.time()
print "  Time (numpy): ", tac - tic
x1 = np.abs(b - np.dot(A,y1))
print "Mean error on b : %f" %(x1.sum() / b.shape[0])

tic = time.time()
for i in xrange(0,20):
    y2 = spams.conjGrad(A,b,x0,tol,itermax)
tac = time.time()
print "  Time (spams): ", tac - tic
x1 = np.dot(A,y2)
x2 = np.abs(b - x1)
print "Mean error on b : %f" %(x2.sum() / b.shape[0])

err = abs(y1 - y2)

7.2  Function spams.bayer

Apply a Bayer pattern to an input image

#
# Name: conjGrad
#
# Usage: spams.conjGrad(A,b,x0 = None,tol = 1e-10,itermax = None)
#
# Description:
#     Conjugate gradient algorithm, sometimes faster than the 
#    equivalent python function solve. In order to solve Ax=b;
#
# Inputs:
#       A:  double square n x n matrix. HAS TO BE POSITIVE DEFINITE
#       b:  double vector of length n.
#       x0: double vector of length n. (optional) initial guess.
#       tol: (optional) tolerance.
#       itermax: (optional) maximum number of iterations.
#
# Output:
#       x: double vector of length n.
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
A = np.asfortranarray(np.random.normal(size = (5000,500)))
A = np.asfortranarray(np.dot(A.T,A),dtype=myfloat)
b = np.ones((A.shape[1],),dtype=myfloat,order="FORTRAN")
x0 = b
tol = 1e-4
itermax = int(0.5 * len(b))

tic = time.time()
for i in xrange(0,20):
    y1 = np.linalg.solve(A,b)
tac = time.time()
print "  Time (numpy): ", tac - tic
x1 = np.abs(b - np.dot(A,y1))
print "Mean error on b : %f" %(x1.sum() / b.shape[0])

tic = time.time()
for i in xrange(0,20):
    y2 = spams.conjGrad(A,b,x0,tol,itermax)
tac = time.time()
print "  Time (spams): ", tac - tic
x1 = np.dot(A,y2)
x2 = np.abs(b - x1)
print "Mean error on b : %f" %(x2.sum() / b.shape[0])

err = abs(y1 - y2)

7.3  Function spams.calcAAt

For an input sparse matrix A, this function returns AAT. For some reasons, when A has a lot more columns than rows, this function can be much faster than the equivalent Matlab command X*A'.

#
# Name: calcAAt
#
# Usage: spams.calcAAt(A)
#
# Description:
#     Compute efficiently AAt = A*A', when A is sparse 
#   and has a lot more columns than rows. In some cases, it is
#   up to 20 times faster than the equivalent python expression
#   AAt=A*A';
#
# Inputs:
#       A:  double sparse m x n matrix   
#
# Output:
#       AAt: double m x m matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
"""
test A * A'
"""

m=200; n = 200000; d= 0.05
A = ssprand(m,n,density=d,format='csc',dtype=myfloat)
result = spams.calcAAt(A)

7.4  Function spams.calcXAt

For an input sparse matrix A and a matrix X, this function returns XAT. For some reasons, when A has a lot more columns than rows, this function can be much faster than the equivalent Matlab command X*A'.

#
# Name: calcXAt
#
# Usage: spams.calcXAt(X,A)
#
# Description:
#     Compute efficiently XAt = X*A', when A is sparse and has a 
#   lot more columns than rows. In some cases, it is up to 20 times 
#   faster than the equivalent python expression;
#
# Inputs:
#       X:  double m x n matrix
#       A:  double sparse p x n matrix   
#
# Output:
#       XAt: double m x p matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
m=200; n = 200000; d= 0.05
A = ssprand(m,n,density=d,format='csc',dtype=myfloat)
X = np.asfortranarray(np.random.normal(size = (64,n)),dtype=myfloat)

result = spams.calcXAt(X,A)

7.5  Function spams.calcXY

For two input matrices X and Y, this function returns XY.

#
# Name: calcXY
#
# Usage: spams.calcXY(X,Y)
#
# Description:
#     Compute Z=XY using the BLAS library used by SPAMS.
#
# Inputs:
#       X:  double m x n matrix
#       Y:  double n x p matrix   
#
# Output:
#       Z: double m x p matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
X = np.asfortranarray(np.random.normal(size = (64,200)),dtype=myfloat)
Y = np.asfortranarray(np.random.normal(size = (200,20000)),dtype=myfloat)
result = spams.calcXY(X,Y)

7.6  Function spams.calcXYt

For two input matrices X and Y, this function returns XYT.

#
# Name: calcXYt
#
# Usage: spams.calcXYt(X,Y)
#
# Description:
#     Compute Z=XY' using the BLAS library used by SPAMS.
#
# Inputs:
#       X:  double m x n matrix
#       Y:  double p x n matrix   
#
# Output:
#       Z: double m x p matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
X = np.asfortranarray(np.random.normal(size = (64,200)),dtype=myfloat)
Y = np.asfortranarray(np.random.normal(size = (20000,200)),dtype=myfloat)
result = spams.calcXYt(X,Y)

7.7  Function spams.calcXtY

For two input matrices X and Y, this function returns XTY.

#
# Name: calcXtY
#
# Usage: spams.calcXtY(X,Y)
#
# Description:
#     Compute Z=X'Y using the BLAS library used by SPAMS.
#
# Inputs:
#       X:  double n x m matrix
#       Y:  double n x p matrix   
#
# Output:
#       Z: double m x p matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
X = np.asfortranarray(np.random.normal(size = (200,64)),dtype=myfloat)
Y = np.asfortranarray(np.random.normal(size = (200,20000)),dtype=myfloat)
result = spams.calcXtY(X,Y)

7.8  Function spams.invSym

For an input symmetric matrices A in ℝn × n, this function returns A−1.

#
# Name: invSym
#
# Usage: spams.invSym(A)
#
# Description:
#     returns the inverse of a symmetric matrix A
#
# Inputs:
#       A:  double n x n matrix   
#
# Output:
#       B: double n x n matrix 
#
# Authors:
# Julien MAIRAL, 2009 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
A = np.asfortranarray(np.random.random(size = (1000,1000)))
A =np.asfortranarray( np.dot(A.T,A),dtype=myfloat)
result = spams.invSym(A)

7.9  Function spams.normalize

#
# Name: normalize
#
# Usage: spams.normalize(A)
#
# Description:
#     rescale the columns of X so that they have
#        unit l2-norm.
#
# Inputs:
#       X:  double m x n matrix   
#
# Output:
#       Y: double m x n matrix 
#
# Authors:
# Julien MAIRAL, 2010 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
A = np.asfortranarray(np.random.random(size = (100,1000)),dtype=myfloat)
res2 = spams.normalize(A)

7.10  Function spams.sort

#
# Name: sort
#
# Usage: spams.sort(X,mode=True)
#
# Description:
#     sort the elements of X using quicksort
#
# Inputs:
#       X:  double vector of size n
#       mode: false for decreasing order (true by default)
#
# Output:
#       Y: double  vector of size n
#
# Authors:
# Julien MAIRAL, 2010 (spams, matlab interface and documentation)
# Jean-Paul CHIEZE 2011-2012 (python interface)
#

The following piece of code illustrates how to use this function. The following piece of code contains usage examples:

import spams
import numpy as np
n = 2000000
X = np.asfortranarray(np.random.normal(size = (n,)),dtype=myfloat)
result = spams.sort(X,True)

7.11  Function displayPatches

Print to the screen a matrix containing as columns image patches.

7.12  Function spams.countPathsDAG

This function counts the number of paths in a DAG using dynamic programming.

#
# The python function is not yet implemented.
#

The following piece of code illustrates how to use this function.

7.13  Function spams.removeCyclesGraph

One heuristic to remove cycles from a graph.

#
# The python function is not yet implemented.
#

The following piece of code illustrates how to use this function.

7.14  Function spams.countConnexComponents

Count the number of connected components of a subgraph from a graph.

#
# The python function is not yet implemented.
#

The following piece of code illustrates how to use this function.

7.15  Function spams.graphOfGroupStruct

#
# Name: graphOfGroupStruct
#
# Usage: spams.graphOfGroupStruct(gstruct)
#
# Description:
#     converts a group structure into the graph structure
#    used by proximalGraph, fistaGraph or structTrainDL
#
# Inputs:
#       gstruct: the structure of groups as a list, one element per node
#     an element is itself a 4 elements list:
#       nodeid (>= 0), weight (double), array of vars associated to the node,
#       array of children (nodeis's)
#
# Output:
#       graph: struct (see documentation of proximalGraph)
#
# Authors:
# Jean-Paul CHIEZE, 2012
#

7.16  Function spams.groupStructOfString

#
# Name: groupStructOfString
#
# Usage: spams.groupStructOfString(s)
#
# Description:
#     decode a multi-line string describing "simply" the structure of groups
#    of variables needed by proximalGraph, proximalTree, fistaGraph,
#    fistaTree and structTrainDL and builds the corresponding group structure.
#    Each line describes a group of variables as a node of a tree.
#    It has up to 4 fields separated by spaces:
#        node-id node-weight [variables-list] -> children-list
#    Let's define Ng = number of groups, and Nv = number of variables.
#    node-id must be in the range (0 - Ng-1), and there must be Ng nodes
#    weight is a float
#    variables-list : a space separated list of integers, maybe empty,
#         but '[' and '] must be present. Numbers in the range (0 - Nv-1)
#    children-list : a space separated list of node-id's
#        If the list is empty, '->' may be omitted.
#    The data must obey some rules : 
#        - A group contains the variables of the corresponding node and of the whole subtree.
#        - Variables attached to a node are those that are not int the subtree.
#        - If the data destination is a Graph, there may be several independant trees,
#          and a varibale may appear in several trees.
#    If the destination is a Tree, there must be only one tree, the root node
#    must have id == 0 and each variable must appear only once.
#
# Inputs:
#       s:  the multi-lines string
#
# Output:
#       groups: list, one element for each node
#                an element is itsel a 4 elements list:
#           nodeid (int >= 0), weight (double), array of vars of the node,
#                array of children (nodeid's)
#
# Authors:
# Jean-Paul CHIEZE, 2012
#

7.17  Function spams.readGroupStruct

#
# Name: readGroupStruct
#
# Usage: spams.readGroupStruct(file)
#
# Description:
#     reads a text file describing "simply" the structure of groups
#    of variables needed by proximalGraph, proximalTree, fistaGraph,
#    fistaTree and structTrainDL and builds the corresponding group structure.
#    weight is a float
#    variables-list : a space separated list of integers, maybe empty,
#        but '[' and '] must be present. Numbers in the range (0 - Nv-1)
#    children-list : a space separated list of node-id's
#        If the list is empty, '->' may be omitted.
#    The data must obey some rules : 
#        - A group contains the variables of the corresponding node and of the whole subtree.
#        - Variables attached to a node are those that are not int the subtree.
#        - If the data destination is a Graph, there may be several independant trees,
#           and a varibale may appear in several trees.
#    If the destination is a Tree, there must be only one tree, the root node
#        must have id == 0 and each variable must appear only once.
#
# Inputs:
#       file:  the file name
#
# Output:
#       groups: list, one element for each node
#                an element is itsel a 4 elements list:
#          nodeid (int >= 0), weight (double), array of vars of the node,
#                array of children (nodeid's)
#
# Authors:
# Jean-Paul CHIEZE, 2012
#

7.18  Function spams.treeOfGroupStruct

#
# Name: treeOfGroupStruct
#
# Usage: spams.treeOfGroupStruct(gstruct)
#
# Description:
#     converts a group structure into the tree structure
#    used by proximalTree, fistaTree or structTrainDL
#
# Inputs:
#       gstruct: the structure of groups as a list, one element per node
#     an element is itself a 4 lements list:
#       nodeid (>= 0), weight (double), array of vars associated to the node,
#       array of children (nodeis's)
#
# Output:
#       permutations: permutation vector that must be applied to the result of the
#               programm using the tree. Empty if no permutation is needed.
#       tree: named list (see documentation of proximalTree)
#       nbvars : number of variables in the tree
#       (permutations,tree,nbvars) = spams.treeOfGroupStruct(gstruct)
#
# Authors:
# Jean-Paul CHIEZE, 2012
#

7.19  Function spams.simpleGroupTree

#
# Name: simpleGroupTree
#
# Usage: spams.simpleGroupTree(degrees)
#
# Description:
#     makes a structure representing a tree given the
#   degree of each level.
#
# Inputs:
#       degrees:  int vector; degrees(i) is the number of children of each node at level i
#
# Output:
#       group_struct: list, one element for each node
#                an element is itsel a 4 elements list :
#           nodeid (int >= 0), weight (double), array of vars attached to the node
#                  (here equal to [nodeid]), array of children (nodeid's)
#
# Authors:
# Jean-Paul CHIEZE, 2012
#

Previous Up Next