The　structural　information　is　critical　in　image　analysis　as　one　of　the　most　popular　topics　in　the　computational　intelligence　area.　To　capture　the　structural　information　of　the　given　images,　the　nuclear-norm　matrix　regression　(NMR)　framework　provides　a　natural　way　by　successfully　formulating　the　two-dimensional　image　error　matrix　into　the　image　analysis.　Nevertheless,　although　NMR　shows　its　powerful　performance　in　robust　face　recognition,　its　intrinsic　regression/classification　mechanism　is　still　unclear,　which　restricts　its　capability.　Furthermore,　since　NMR　works　in　a　sample-dependent　scheme,　it　requires　remodelling　for　each　given　image　sample　and　leads　to　a　failure　in　learning　the　intrinsic　and　structural　information　from　the　given　image　samples.　Leveraging　the　superiority　and　drawbacks　of　the　NMR　framework,　in　this　paper,　we　propose　Probabilistic　Nuclear-norm　Matrix　Regression　(PNMR).　We　form　the　idea　of　PNMR　with　theoretical　deduction　using　Bayesian　inference　to　clearly　show　its　probability　interpretation,　where　we　present　a　unified　as　well　as　a　delicated　formulation　for　optimization.　PNMR　can　be　proven　to　achieve　the　joint　learning　of　the　NMR-style　formulation　regularized　by　the　$L_{2,1}$-norm,　making　it　adaptive　to　arbitrary　given　image　samples.　To　fully　consider　the　intrinsic　relationships　of　the　observed　samples,　we　propose　the　Probabilistic　Nuclear-norm　Matrix　Regression　regularized　by　Random　Graph　(PNMR-RG)　on　the　basis　of　PNMR.　Extensive　experiments　on　several　image　datasets　were　performed　and　comparisons　were　made　with　10　state-of-the-art　methods　to　demonstrate　the　feasibility　and　promising　performance　of　both　PNMR　and　PNMR-RG.