Returns a manifold struct to optimize over real matrices with given sparsity pattern. function M = euclideansparsefactory(A) Returns M, a structure describing the Euclidean space of real matrices with a fixed sparsity pattern. This linear manifold is equipped with the standard Frobenius distance and associated trace inner product, and is usable as a Riemannian manifold for Manopt. The matrices are represented as sparse matrices. Their sparsity pattern is fixed. The tangent vectors are represented in the same way as points since this is a Euclidean space. Point and vectors in the embedding space, that is, in the space of (possibly full) matrices of the same size as A, are represented as matrices of the same size as A, full or sparse, real. The current code relies on Matlab's built-in representation of sparse matrices, which has the inconvenient effect that we cannot control the sparsity structure: if entries of points or tangent vectors which are allowed to be nonzero (by the sparsity structure) happen to be zero, then Matlab internally restructures the sparse matrix, which may be costly, and which may increase computation time when using that matrix in combination with other sparse matrices. There is also no built-in way to let Matlab know that two matrices have the same sparsity structure. For this reason, in a future update, it will be good to try to represent points and tangent vectors internally as vectors of nonzeros, with truly fixed sparsity pattern. In the meantime, this factory is provided for convenience and prototyping, bearing in mind it is likely not efficient. See also: euclideanfactory euclideancomplexfactory
0001 function M = euclideansparsefactory(A) 0002 % Returns a manifold struct to optimize over real matrices with given sparsity pattern. 0003 % 0004 % function M = euclideansparsefactory(A) 0005 % 0006 % Returns M, a structure describing the Euclidean space of real matrices 0007 % with a fixed sparsity pattern. This linear manifold is equipped with 0008 % the standard Frobenius distance and associated trace inner product, 0009 % and is usable as a Riemannian manifold for Manopt. 0010 % 0011 % The matrices are represented as sparse matrices. Their sparsity pattern 0012 % is fixed. The tangent vectors are represented in the same way as points 0013 % since this is a Euclidean space. Point and vectors in the embedding space, 0014 % that is, in the space of (possibly full) matrices of the same size as A, 0015 % are represented as matrices of the same size as A, full or sparse, real. 0016 % 0017 % The current code relies on Matlab's built-in representation of sparse 0018 % matrices, which has the inconvenient effect that we cannot control the 0019 % sparsity structure: if entries of points or tangent vectors which are 0020 % allowed to be nonzero (by the sparsity structure) happen to be zero, 0021 % then Matlab internally restructures the sparse matrix, which may be 0022 % costly, and which may increase computation time when using that matrix 0023 % in combination with other sparse matrices. There is also no built-in way 0024 % to let Matlab know that two matrices have the same sparsity structure. 0025 % For this reason, in a future update, it will be good to try to represent 0026 % points and tangent vectors internally as vectors of nonzeros, with truly 0027 % fixed sparsity pattern. In the meantime, this factory is provided for 0028 % convenience and prototyping, bearing in mind it is likely not efficient. 0029 % 0030 % See also: euclideanfactory euclideancomplexfactory 0031 0032 % This file is part of Manopt: www.manopt.org. 0033 % Original author: Bamdev Mishra, Mar. 28, 2019. 0034 % Change log: 0035 % May 3, 2019 (NB): adapted many functions to take advantage of sparsity a bit more. 0036 0037 dimensions_vec = size(A); 0038 assert(length(dimensions_vec) == 2, 'A should be a matrix (or a vector).'); 0039 [I, J] = find(A); 0040 nvals = length(I); 0041 S = sparse(I, J, ones(nvals, 1), dimensions_vec(1), dimensions_vec(2), nvals); 0042 0043 M.size = @() dimensions_vec; 0044 0045 M.name = @() sprintf('Euclidean space R^(%dx%d) with fixed sparsity pattern containg %d non-zero entries', ... 0046 dimensions_vec(1), dimensions_vec(2), nvals); 0047 0048 M.dim = @() nvals; 0049 0050 M.inner = @(x, d1, d2) d1(:).'*d2(:); % nonzeros(d1).'*nonzeros(d2); might not work since d1, d2 might have extra zeros 0051 0052 M.norm = @(x, d) norm(d, 'fro'); 0053 0054 M.dist = @(x, y) norm(x-y, 'fro'); 0055 0056 M.typicaldist = @() sqrt(prod(dimensions_vec)); 0057 0058 M.proj = @(x, d) S.*d; % could replace with: d(ind) where ind = find(S); which is faster? 0059 0060 M.egrad2rgrad = @(x, g) S.*g; 0061 0062 M.ehess2rhess = @(x, eg, eh, d) S.*eh; 0063 0064 M.tangent = M.proj; 0065 0066 M.exp = @exp; 0067 function y = exp(x, d, t) 0068 if nargin == 3 0069 y = x + t*d; 0070 else 0071 y = x + d; 0072 end 0073 end 0074 0075 M.retr = M.exp; 0076 0077 M.log = @(x, y) y-x; 0078 0079 M.hash = @(x) ['z' hashmd5(nonzeros(x))]; 0080 0081 M.rand = @() sprandn(S); 0082 0083 M.randvec = @randvec; 0084 function u = randvec(x) %#ok<INUSD> 0085 u = sprandn(S); 0086 u = u / norm(u, 'fro'); 0087 end 0088 0089 M.lincomb = @matrixlincomb; 0090 0091 M.zerovec = @(x) spalloc(dimensions_vec(1), dimensions_vec(2), nvals); 0092 0093 M.transp = @(x1, x2, d) d; 0094 M.isotransp = M.transp; % the transport is isometric 0095 0096 M.pairmean = @(x1, x2) .5*(x1+x2); 0097 0098 M.vec = @(x, u_mat) nonzeros(u_mat); 0099 M.mat = @(x, u_vec) sparse(I, J, u_vec, m, n, nvals); 0100 M.vecmatareisometries = @() true; 0101 0102 end