core/vnl/algo/vnl_svd_fixed.h
Go to the documentation of this file.
00001 // This is core/vnl/algo/vnl_svd_fixed.h
00002 #ifndef vnl_svd_fixed_h_
00003 #define vnl_svd_fixed_h_
00004 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00005 #pragma interface
00006 #endif
00007 //:
00008 // \file
00009 // \brief Holds the singular value decomposition of a vnl_matrix_fixed.
00010 // \author Andrew W. Fitzgibbon, Ian Scott
00011 // \date   12 Oct 2009
00012 //
00013 
00014 #include <vnl/vnl_numeric_traits.h>
00015 #include <vnl/vnl_vector_fixed.h>
00016 #include <vnl/vnl_matrix_fixed.h>
00017 #include <vnl/vnl_diag_matrix_fixed.h>
00018 #include <vcl_iosfwd.h>
00019 
00020 //: Holds the singular value decomposition of a vnl_matrix_fixed.
00021 //
00022 //  The class holds three matrices U, W, V such that the original matrix
00023 //  $M = U W V^\top$.  The DiagMatrix W stores the singular values in decreasing
00024 //  order.  The columns of U which correspond to the nonzero singular values
00025 //  form a basis for range of M, while the columns of V corresponding to the
00026 //  zero singular values are the nullspace.
00027 //
00028 //  The SVD is computed at construction time, and inquiries may then be made
00029 //  of the SVD.  In particular, this allows easy access to multiple
00030 //  right-hand-side solves without the bother of putting all the RHS's into a
00031 //  Matrix.
00032 //
00033 
00034 export template <class T, unsigned int R, unsigned int C>
00035 class vnl_svd_fixed
00036 {
00037  public:
00038   //: The singular values of a matrix of complex<T> are of type T, not complex<T>
00039   typedef typename vnl_numeric_traits<T>::abs_t singval_t;
00040 
00041   //:
00042   // Construct a vnl_svd_fixed<T> object from $m \times n$ matrix $M$.  The
00043   // vnl_svd_fixed<T> object contains matrices $U$, $W$, $V$ such that
00044   // $U W V^\top = M$.
00045   //
00046   // Uses linpack routine DSVDC to calculate an ``economy-size'' SVD
00047   // where the returned $U$ is the same size as $M$, while $W$
00048   // and $V$ are both $n \times n$.  This is efficient for
00049   // large rectangular solves where $m > n$, typical in least squares.
00050   //
00051   // The optional argument zero_out_tol is used to mark the zero singular
00052   // values: If nonnegative, any s.v. smaller than zero_out_tol in
00053   // absolute value is set to zero.  If zero_out_tol is negative, the
00054   // zeroing is relative to |zero_out_tol| * sigma_max();
00055 
00056   vnl_svd_fixed(vnl_matrix_fixed<T,R,C> const &M, double zero_out_tol = 0.0);
00057  ~vnl_svd_fixed() {}
00058 
00059   // Data Access---------------------------------------------------------------
00060 
00061   //: find weights below threshold tol, zero them out, and update W_ and Winverse_
00062   void            zero_out_absolute(double tol = 1e-8); //sqrt(machine epsilon)
00063 
00064   //: find weights below tol*max(w) and zero them out
00065   void            zero_out_relative(double tol = 1e-8); //sqrt(machine epsilon)
00066   int             singularities () const { return W_.rows() - rank(); }
00067   unsigned int    rank () const { return rank_; }
00068   singval_t       well_condition () const { return sigma_min()/sigma_max(); }
00069 
00070   //: Calculate determinant as product of diagonals in W.
00071   singval_t       determinant_magnitude () const;
00072   singval_t       norm() const;
00073 
00074   //: Return the matrix U.
00075   vnl_matrix_fixed<T,R,C>      & U()       { return U_; }
00076 
00077   //: Return the matrix U.
00078   vnl_matrix_fixed<T,R,C> const& U() const { return U_; }
00079 
00080   //: Return the matrix U's (i,j)th entry (to avoid svd.U()(i,j); ).
00081   T U(int i, int j) const { return U_(i,j); }
00082 
00083   //: Get at DiagMatrix (q.v.) of singular values, sorted from largest to smallest
00084   vnl_diag_matrix_fixed<singval_t, C>       & W()             { return W_; }
00085 
00086   //: Get at DiagMatrix (q.v.) of singular values, sorted from largest to smallest
00087   vnl_diag_matrix_fixed<singval_t, C> const & W() const       { return W_; }
00088   vnl_diag_matrix_fixed<singval_t, C>       & Winverse()      { return Winverse_; }
00089   vnl_diag_matrix_fixed<singval_t, C> const & Winverse() const { return Winverse_; }
00090   singval_t                   & W(int i, int j) { return W_(i,j); }
00091   singval_t                   & W(int i)        { return W_(i,i); }
00092   singval_t     sigma_max() const { return W_(0,0); }       // largest
00093   singval_t     sigma_min() const { return W_(C-1,C-1); } // smallest
00094 
00095   //: Return the matrix V.
00096   vnl_matrix_fixed<T,C,C>      & V()       { return V_; }
00097 
00098   //: Return the matrix V.
00099   vnl_matrix_fixed<T,C,C> const& V() const { return V_; }
00100 
00101   //: Return the matrix V's (i,j)th entry (to avoid svd.V()(i,j); ).
00102   T V(int i, int j) const { return V_(i,j); }
00103 
00104   //:
00105   inline vnl_matrix_fixed<T,C,R> inverse () const { return pinverse(); }
00106 
00107   //: pseudo-inverse (for non-square matrix) of desired rank.
00108   vnl_matrix_fixed<T,C,R> pinverse (unsigned int rank = ~0u) const; // ~0u == (unsigned int)-1
00109 
00110   //: Calculate inverse of transpose, using desired rank.
00111   vnl_matrix_fixed<T,R,C> tinverse (unsigned int rank = ~0u) const; // ~0u == (unsigned int)-1
00112 
00113   //: Recompose SVD to U*W*V', using desired rank.
00114   vnl_matrix_fixed<T,R,C> recompose (unsigned int rank = ~0u) const; // ~0u == (unsigned int)-1
00115 
00116   //: Solve the matrix equation M X = B, returning X
00117   vnl_matrix<T> solve (vnl_matrix<T> const& B) const;
00118 
00119   //: Solve the matrix-vector system M x = y, returning x.
00120   vnl_vector_fixed<T, C> solve (vnl_vector_fixed<T, R> const& y) const;
00121   void          solve (T const *rhs, T *lhs) const; // min ||A*lhs - rhs||
00122 
00123   //: Solve the matrix-vector system M x = y.
00124   // Assuming that the singular values W have been preinverted by the caller.
00125   void solve_preinverted(vnl_vector_fixed<T,R> const& rhs, vnl_vector_fixed<T,C>* out) const;
00126 
00127   //: Return N such that M * N = 0
00128   vnl_matrix<T> nullspace() const;
00129 
00130   //: Return N such that M' * N = 0
00131   vnl_matrix<T> left_nullspace() const;
00132 
00133   //: Return N such that M * N = 0
00134   vnl_matrix<T> nullspace(int required_nullspace_dimension) const;
00135 
00136   //: Implementation to be done yet; currently returns left_nullspace(). - PVR.
00137   vnl_matrix<T> left_nullspace(int required_nullspace_dimension) const;
00138 
00139   //: Return the rightmost column of V.
00140   //  Does not check to see whether or not the matrix actually was rank-deficient -
00141   // the caller is assumed to have examined W and decided that to his or her satisfaction.
00142   vnl_vector_fixed<T,C> nullvector() const;
00143 
00144   //: Return the rightmost column of U.
00145   //  Does not check to see whether or not the matrix actually was rank-deficient.
00146   vnl_vector_fixed<T,R> left_nullvector() const;
00147 
00148   bool valid() const { return valid_; }
00149 
00150  private:
00151 
00152   vnl_matrix_fixed<T, R, C> U_;        // Columns Ui are basis for range of M for Wi != 0
00153   vnl_diag_matrix_fixed<singval_t, C> W_;// Singular values, sorted in decreasing order
00154   vnl_diag_matrix_fixed<singval_t, C> Winverse_;
00155   vnl_matrix_fixed<T, C, C> V_;       // Columns Vi are basis for nullspace of M for Wi = 0
00156   unsigned rank_;
00157   bool have_max_;
00158   singval_t max_;
00159   bool have_min_;
00160   singval_t min_;
00161   double last_tol_;
00162   bool valid_;        // false if the NETLIB call failed.
00163 
00164   // Disallow assignment.
00165   vnl_svd_fixed<T,R,C>(vnl_svd_fixed<T,R,C> const &) { }
00166   vnl_svd_fixed<T,R,C>& operator=(vnl_svd_fixed<T,R,C> const &) { return *this; }
00167 };
00168 
00169 template <class T, unsigned int R, unsigned int C>
00170 inline
00171 vnl_matrix_fixed<T,C,R> vnl_svd_fixed_inverse(vnl_matrix_fixed<T,R,C> const& m)
00172 {
00173   return vnl_svd_fixed<T,R,C>(m).inverse();
00174 }
00175 
00176 export template <class T, unsigned int R, unsigned int C>
00177 vcl_ostream& operator<<(vcl_ostream&, vnl_svd_fixed<T,R,C> const& svd);
00178 
00179 #endif // vnl_svd_fixed_h_