Manifold of tensors of fixed Tensor Train (TT) rank, embedded geometry NOTE: this manifold requires the use of a modified version of TTeMPS_1.1, which is packaced with Manopt and can be found in /manopt/manifolds/ttfixedrank/TTeMPS_1.1/ function M = fixedTTrankfactory(n, r) function M = fixedTTrankfactory(n, r, ind) Inputs: n is a vector denoting the embedding space dimension, R^{n(1) x ... x n(d)} (d = length(n) is the order of the tensor) r is a vector denoting the TT-rank of all tensors in the manifold, where length(r) = d + 1. We also enforce r(1) = r(d+1) = 1. ind (optional): if only sparse tensors in the embedding space are considered (as is the case for tensor completion in particular), the parameter ind can be passed, where ind is a matrix of size p-by-d whose rows contain the multi-indices of the p non-zero entries. See TTeMPS_1.1/algorithms/completion/makeOmegaSet.m for an example on constructing ind. A point X on the manifold is represented through its TT-cores, stored in the cell array X.U. We enforce the TT-cores in X.U to be 'left-orthogonalized' (see Steinlechner's thesis, Section 4.2.1), because many algorithms require X.U to be left-orthogonalized. A tangent vector Z in the tangent space of a TT-tensor X is represented as a structure containing 3 cell-arrays: 1) Z.U, which is exactly X.U of the base point X 2) Z.V, the right-orthogonalization of X.U 3) Z.dU, the 'variational cores' that parametrize the tangent vector Z itself. This matches the 'alternative representation' of tangent vectors discussed in the Psenka and Boumal paper (see below). The first-order Riemannian geometry of the manifold of fixed TT-rank tensors is described in detail in Steinlechner's PhD thesis, Section 4: https://infoscience.epfl.ch/record/217938?ln=en TTeMPS also comes from that work. The second-order Riemannian geometry (necessary for the ehess2rhess tool) is described in the following paper: Psenka and Boumal, Second-order optimization for tensors with fixed tensor-train rank, Optimization workshop at NeurIPS 2020. https://arxiv.org/abs/2011.13395 Please cite the Manopt paper as well as the relevant research papers. See also: fixedrankembeddedfactory fixedranktensorembeddedfactory
0001 function M = fixedTTrankfactory(n, r, ind) 0002 % Manifold of tensors of fixed Tensor Train (TT) rank, embedded geometry 0003 % 0004 % NOTE: this manifold requires the use of a modified version of TTeMPS_1.1, 0005 % which is packaced with Manopt and can be found in 0006 % /manopt/manifolds/ttfixedrank/TTeMPS_1.1/ 0007 % 0008 % function M = fixedTTrankfactory(n, r) 0009 % function M = fixedTTrankfactory(n, r, ind) 0010 % 0011 % Inputs: 0012 % n is a vector denoting the embedding space dimension, 0013 % R^{n(1) x ... x n(d)} (d = length(n) is the order of the tensor) 0014 % r is a vector denoting the TT-rank of all tensors in the manifold, 0015 % where length(r) = d + 1. We also enforce r(1) = r(d+1) = 1. 0016 % ind (optional): if only sparse tensors in the embedding space are 0017 % considered (as is the case for tensor completion in particular), the 0018 % parameter ind can be passed, where ind is a matrix of size p-by-d 0019 % whose rows contain the multi-indices of the p non-zero entries. 0020 % See TTeMPS_1.1/algorithms/completion/makeOmegaSet.m for an example 0021 % on constructing ind. 0022 % 0023 % A point X on the manifold is represented through its TT-cores, stored in 0024 % the cell array X.U. We enforce the TT-cores in X.U to be 0025 % 'left-orthogonalized' (see Steinlechner's thesis, Section 4.2.1), because 0026 % many algorithms require X.U to be left-orthogonalized. 0027 % 0028 % A tangent vector Z in the tangent space of a TT-tensor X is represented 0029 % as a structure containing 3 cell-arrays: 0030 % 0031 % 1) Z.U, which is exactly X.U of the base point X 0032 % 2) Z.V, the right-orthogonalization of X.U 0033 % 3) Z.dU, the 'variational cores' that parametrize the tangent vector Z 0034 % itself. This matches the 'alternative representation' of tangent 0035 % vectors discussed in the Psenka and Boumal paper (see below). 0036 % 0037 % The first-order Riemannian geometry of the manifold of fixed TT-rank 0038 % tensors is described in detail in Steinlechner's PhD thesis, Section 4: 0039 % https://infoscience.epfl.ch/record/217938?ln=en 0040 % TTeMPS also comes from that work. 0041 % 0042 % The second-order Riemannian geometry (necessary for the ehess2rhess tool) 0043 % is described in the following paper: 0044 % Psenka and Boumal, 0045 % Second-order optimization for tensors with fixed tensor-train rank, 0046 % Optimization workshop at NeurIPS 2020. 0047 % https://arxiv.org/abs/2011.13395 0048 % 0049 % Please cite the Manopt paper as well as the relevant research papers. 0050 % 0051 % See also: fixedrankembeddedfactory fixedranktensorembeddedfactory 0052 0053 % This file is part of Manopt: www.manopt.org. 0054 % Original author: Michael Psenka, Nov. 24, 2020. 0055 % Contributors: Nicolas Boumal 0056 % Change log: 0057 0058 % Order of tensors 0059 d = numel(n); 0060 0061 assert(length(r) == d+1, ... 0062 'Vector r must have length equal to length(n)+1.'); 0063 assert(r(1) == 1 && r(end) == 1, ... 0064 'The first and last entry of r must be equal to 1.'); 0065 0066 M.name = @() sprintf('Manifold of tensor order %d, dimension %s, and TT-rank %s', ... 0067 d, mat2str(n), mat2str(r)); 0068 0069 M.dim = @dim; 0070 function k = dim() 0071 k = 0; 0072 0073 for m = 1:(d-1) 0074 k = k + r(m) * n(m) * r(m + 1) - r(m + 1) * r(m + 1); 0075 end 0076 0077 k = k + r(d) * n(d) * r(d + 1); 0078 end 0079 0080 % Creates random unit-norm TT-tensor of TT-rank r. 0081 M.rand = @random; 0082 function X = random() 0083 % Gaussian random cores 0084 X = TTeMPS_randn(r, n); 0085 % Left-orthogonalize X 0086 X = orthogonalize(X, d); 0087 % Normalize (efficient transformation to unit norm) 0088 X.U{d} = (1 / norm(X.U{d})) * X.U{d}; 0089 end 0090 0091 % Uses the TT-SVD algorithm to project a full array to a TT-tensor 0092 % of TT-rank r 0093 M.from_array = @fromArray; 0094 0095 function X = fromArray(Y) 0096 % TTeMPS implementation of TT-SVD 0097 X = TTeMPS.from_array(Y, r); 0098 % Left-orthogonalized version of X 0099 X = orthogonalize(X, d); 0100 end 0101 0102 % Creates random unit norm tangent vector at X on manifold. 0103 % Optional argument Xr of right-orthogonalized X. 0104 M.randvec = @randomTangent; 0105 function Z = randomTangent(X, Xr) 0106 if nargin == 1 0107 % If not provided, right orthogonalize X 0108 Xr = orthogonalize(X, 1); % right-orthogonalized version of X 0109 end 0110 0111 % Two arguments --> random unit-norm tangent vector 0112 Z = TTeMPS_tangent_orth(X, Xr); 0113 end 0114 0115 M.zerovec = @zeroVector; 0116 function Z0 = zeroVector(X) 0117 % X could be given as base point or tangent vector 0118 if isa(X, 'TTeMPS') 0119 % For TTeMPS function, one argument --> zero vec at point 0120 Z0 = TTeMPS_tangent_orth(X); 0121 elseif isa(X, 'TTeMPS_tangent_orth') 0122 % If tangent vec, simply set dU cores to 0 0123 Z0 = X; 0124 for k = 1:d 0125 Z0.dU{k} = zeros(r(k), n(k), r(k + 1)); 0126 end 0127 else 0128 error('unexpected input type for zerovec') 0129 end 0130 0131 end 0132 0133 % Note that innerprod has an overflow in TTeMPS for TT-tensor arguments 0134 M.inner = @(x, u, v) innerprod(u, v); 0135 M.norm = @(x, v) real(sqrt(innerprod(v, v))); 0136 M.dist = @(x, y) error('tensor_fixed_TT_rank_factory.dist not implemented yet.'); 0137 M.typicaldist = @() M.dim(); 0138 0139 0140 % Given Z in tangent vector format, projects the components U_i such 0141 % that they satisfy the tangent space constraints up to numerical 0142 % errors (i.e., enforce that they satisfy the so-called gauge 0143 % conditions). If Z was indeed a tangent vector at X, this should 0144 % barely affect Z (it would not at all if we had infinite numerical 0145 % accuracy). 0146 M.tangent = @tangent; 0147 function Z = tangent(X, Zin) 0148 % Project to normal spaces of U^L for all but the last core 0149 Z = Zin; % this copies the TTeMPS_tangent_orth class structure 0150 for k = 1:(d-1) 0151 dUL = unfold(Zin.dU{k}, 'left'); 0152 UL = unfold(X.U{k}, 'left'); 0153 dUL_new = dUL - UL * (UL' * dUL); 0154 r = Z.rank; 0155 n = Z.size; 0156 Z.dU{k} = reshape(dUL_new, [r(k), n(k), r(k + 1)]); 0157 end 0158 end 0159 0160 0161 % It would be useful to implement the following efficienctly. 0162 % 0163 % Applies a linear transformation to tensor W. 0164 % Z is a matrix, and W is a tensor, which must be flattened into a 0165 % vector before applying Z. 0166 % function ZW = apply_matrix(Z, W) 0167 % ... 0168 % end 0169 % 0170 % Same as apply_ambient, but applies Z' to W. 0171 % function ZtW = apply_matrix_transpose(Z, W) 0172 % ... 0173 % end 0174 0175 % Compute linear combination of two TT-tensors. 0176 % Note that '+' and scalar multiplication are both overloaded in the 0177 % TTeMPS library. 0178 M.lincomb = @matrixlincomb; 0179 0180 0181 % Orthogonal projection of an ambient vector Z represented as full 0182 % array of size n to the tangent space of TT-tensor Z. 0183 % Two possible calls: either xR (right orthogonalized) is known or not. 0184 M.proj = @projection; 0185 function Zproj = projection(X, Z) 0186 0187 Xr = orthogonalize(X, 1); %right-orthogonalized version of X 0188 0189 % Check if using sparse ambient space 0190 if exist('ind', 'var') 0191 Zproj = TTeMPS_tangent_orth(X, Xr, Z, ind); 0192 else 0193 Zproj = TTeMPS_tangent_orth(X, Xr, Z); 0194 end 0195 0196 end 0197 0198 M.egrad2rgrad = @projection; 0199 0200 0201 % Given the Euclidean gradient at X and the Euclidean Hessian at X 0202 % along H, where egrad and ehess are vectors in the ambient space and H 0203 % is a tangent vector at X, returns the Riemannian Hessian at X along 0204 % H, which is a tangent vector. 0205 % Curvature part denotes the Weingarten map part. Euclidean part is the 0206 % Euclidean hessian projection part, 0207 M.ehess2rhess = @ehess2rhess; 0208 function rhess = ehess2rhess(X, egrad, ehess, H) 0209 0210 % Euclidean part 0211 rhess = projection(X, ehess); 0212 0213 % Curvature part 0214 if exist('ind', 'var') 0215 rhess = rhess + TT_weingarten(H, egrad, ind); 0216 else 0217 rhess = rhess + TT_weingarten(H, egrad); 0218 end 0219 end 0220 0221 % Converts a tangent vector to the TT format 0222 M.tangent2TT = @tangent2TT; 0223 function Z_TT = tangent2TT(X, Z) %#ok<INUSL> 0224 Z_TT = tangent_to_TTeMPS(Z); 0225 end 0226 0227 % It would be useful to implement the following more efficiently... 0228 M.tangent2ambient = @tangent2ambient; 0229 function Zamb = tangent2ambient(X, Z) %#ok<INUSL> 0230 Zamb = full(Z); 0231 end 0232 0233 % Retraction for the fixed TT - rank manifold 0234 M.retr = @retraction; 0235 0236 % NOTE: X not used in the function because Z is 0237 % a structure that contains all information of 0238 % X. X is kept as an argument to keep consistency 0239 % with standard manifold factory format 0240 function Y = retraction(X, Z, t) %#ok<INUSL> 0241 0242 if nargin < 3 0243 t = 1; 0244 end 0245 0246 Y = tangentAdd(Z, t, true); 0247 Y = orthogonalize(Y, d); 0248 0249 end 0250 0251 % Vector transport (see Steinlechner's thesis) 0252 % Computes a tangent vector at X2 that "looks like" the tangent vector 0253 % Z1 at X1. This is not necessarily a parallel transport. 0254 M.transp = @project_tangent; 0255 function Z2 = project_tangent(X1, X2, Z1) %#ok<INUSL> 0256 Z2 = projection(X2, Z1); 0257 end 0258 0259 % The function 'vec' is isometric from the tangent space at X to real 0260 % vectors by flattening dU cores and stringing out to one vector. 0261 % The function 'mat' is the left-inverse of 'vec'. It is sometimes 0262 % useful to apply 'tangent' to the output of 'mat'. 0263 M.vec = @vec; 0264 function Zvec = vec(X, Z) %#ok<INUSL> 0265 X_size = 0; 0266 for k = 1:d 0267 X_size = X_size + numel(Z.dU{k}); 0268 end 0269 % initialize full flattened vector in memory 0270 Zvec = zeros(X_size,1); 0271 % starting index to fill Zvec 0272 ind_start = 1; 0273 % how many entries to fill Zvec 0274 ind_step = numel(Z.dU{1}); 0275 for k = 1:d 0276 Zvec(ind_start:ind_start+ind_step-1) = Z.dU{k}(:); 0277 ind_start = ind_start+ind_step; 0278 if k < d % avoids indexing error at end of loop 0279 ind_step = numel(Z.dU{k+1}); 0280 end 0281 end 0282 end 0283 0284 M.mat = @mat; 0285 function Zmat = mat(X, Zvec) 0286 Zmat = M.zerovec(X); 0287 for k = 1:d 0288 sizeSubVec = numel(Zmat.dU{k}); % how many elements from Zvec belong to dU{k} 0289 Zmat.dU{k} = reshape(Zvec(1:sizeSubVec), size(Zmat.dU{k})); 0290 Zvec = Zvec((sizeSubVec+1):end); 0291 end 0292 0293 end 0294 0295 % That vec/mat are isometries is checked in the Psenka & Boumal paper, 0296 % in relation to the discussion of an alternative parametrization of 0297 % the tangent spaces. 0298 M.vecmatareisometries = @() true; 0299 0300 end